Given a binary search tree (BST) and an integer k, find k-th smallest element.
The 3rd smallest element is 3.
Input Format: There are two arguments in the input. First one is the root of the BST and second one is an integer k.
Output: Return an integer, the k-th smallest element of the BST.
● 1 <= number of nodes in the BST <= 6000
● 1 <= k <= number of nodes
● -2 * 10^9 <= value stored in any node <= 2 * 10^9
● You are not allowed to alter the given BST in any way.
We want to find kth smallest element of the given BST. If we can get all the elements of BST in sorted order then our answer will be the kth element. We know that in-order traversal visits elements in the sorted order! But the time complexity of such a solution would be O(N) and auxiliary space used is also O(N).
Note that we don’t need to store all the elements, we can just keep the count of visited nodes; when the counter becomes k it is the node we want!
Your code should look like:
void modified_inorder(root, k)
handle base case;
if (answer is not found in left subtree)
// make sure that you are incrementing
// after the left subtree is visited.
consider current node;
In terms of the number of tree nodes, it is O(N). Using other variables we can write a tighter bound for this solution. In terms of the height of the tree h and k, it is O(h + k).
The algorithm first traverses down to the leftmost node which takes O(h) time, then traverses k elements in O(k) time. Therefore overall time complexity is O(h + k).
Note that even if k=1 the algorithm has to go all the way down the tree to find the smallest element, visiting all the nodes on the way, and visiting one node takes constant time. So far we have used O(h) time where h is the height of the tree (worst case is when the leftmost leaf of the tree is the longest one).
Having gone all the way down to the smallest element, the algorithm then visits exactly k nodes from there (still constant time per node); complexity so far is O(h) + O(k).
Having found and saved the k-th element value, the algorithm still needs to pop out from the recursion calls so that it can return the answer in the end. For that it will use constant time per level of recursion, per depth of the tree (worst case, again, is when we have found the k-th element in the leaf of the longest branch of the tree). That takes another O(h) time. Therefore the overall time complexity: O(h) + O(k) + O(h) = O(2h + k) = O(h + k).
O(h) due to the stack frames for the recursive calls.
O(N) due to input size.