Finding the kth smallest element in the binary search tree

Question

I was trying to solve this problem from leetcode and the prompt looks like this:

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it. https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/

class Solution {
   public int kthSmallest(TreeNode root, int k) {
       TreeNode curr = new TreeNode(0);
       ArrayList<TreeNode> res = new ArrayList<TreeNode>();
       res = inOrder(root);
       if(res != null){
           curr = res.get(k);
           return curr.val;
       }
       return -1; //if not found
   }
   
   public ArrayList<TreeNode> inOrder(TreeNode root){ //the value of the nodes would be in increasing order 
       ArrayList<TreeNode> list = new ArrayList<TreeNode>();
       if(root == null){
           return list;
       }
       list.addAll(inOrder(root.left));
       list.addAll(inOrder(root));
       list.addAll(inOrder(root.right));
       return list;
   }
}

However, the system gave me the "memory limit exceeded" error message, is my logic faulted or is there anyway I could fix my code? Thanks in advance!

@Emma this one: leetcode.com/problems/kth-smallest-element-in-a-bst/description — CSnewbie
list.addAll(inOrder(root)); == infinite recursion. Should just be adding the root node here. — Jim Garrison

Emma Emma · Accepted Answer · 2020-08-16T04:05:14

Your logic is probably fine, however should be an efficiency issue since you're getting MLE. It seems you're using two extra spaces, which we won't need that for solving this problem.

This'll pass in Java:

public final class Solution {
    private static int res = 0;
    private static int count = 0;

    public final int kthSmallest(
        final TreeNode root, 
        final int k
    ) {
        count = k;
        inorder(root);
        return res;
    }

    private final void inorder(
        final TreeNode node
    ) {
        if (node.left != null)
            inorder(node.left);
        count--;
        if (count == 0) {
            res = node.val;
            return;
        }
        if (node.right != null)
            inorder(node.right);
    }
}

and here is a Python version, if you'd be interested, similarly with inorder traversal:

class Solution:
    def kthSmallest(self, root, k):
        def inorder(node):
            if not node:
                return
            inorder(node.left)
            self.k -= 1
            if self.k == 0:
                self.res = node.val
                return
            inorder(node.right)

        self.k, self.res = k, None
        inorder(root)
        return self.res

References

For additional details, please see the Discussion Board where you can find plenty of well-explained accepted solutions with a variety of languages including low-complexity algorithms and asymptotic runtime/memory analysis^{1, 2}.
Brute force algorithms usually get accepted for easy questions. For medium and hard questions, brute force algorithms mostly fail with Time Limit Exceeded (TLE) and less with Memory Limit Exceeded (MLE) errors.

Finding the kth smallest element in the binary search tree

1 Answers

References