Problem
Given the root of a Binary Search Tree (BST) and an integer k, return the kth smallest value among all the nodes in the tree.In a BST, an inorder traversal visits the nodes in ascending sorted order.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
root = [3,1,4,null,2]
k = 1
3
/ \
1 4
\
2
Output
1 Input
root = [5,3,6,2,4,null,null,1]
k = 3
5
/ \
3 6
/ \
2 4
/
1
Output
3 Solution
This solution uses an iterative inorder traversal with a Stack. Since inorder traversal of a BST visits nodes in ascending order, the kth visited node is the kth smallest element.We first push all left nodes onto the stack. Then, we process the top node, decrement k, and move to its right subtree.
When k becomes
0, the current node contains the kth smallest value.
public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
// Traverse to the leftmost node.
while (current != null) {
stack.push(current);
current = current.left;
}
// Process the next smallest node.
current = stack.pop();
if (--k == 0) {
return current.val;
}
// Move to the right subtree.
current = current.right;
}
return -1;
}
Complexity
In the worst case, the algorithm may visit all n nodes, resulting in a time complexity ofO(n).
The stack can contain up to h nodes, where h is the height of the tree, resulting in an extra space complexity of
O(h).