Kth Smallest Element in a BST
Given the root of a binary search tree, and an integer k, return the kth smallest element in the BST.
Constraints:
- The number of nodes in the tree is in the range [1, 10^4].
- 1 <= k <= n.
- Follow up: If the BST is modified often (i.e., we can insert/delete nodes of the BST), how would you optimize your findKthSmallest routine?
Examples:
Input: [3,1,4,null,2], k = 1
Output: 1
Explanation: The first smallest element is 1.
Input: [5,3,6,2,4,null,null,1], k = 3
Output: 3
Explanation: The third smallest element is 3.
Solutions
Inorder Traversal
Time: O(n)Space: O(n)
We use a stack to store the nodes of the BST. We start from the root and keep going left until we reach a null node. Then we pop a node from the stack, decrement k, and if k is 0, we return the value of the current node. Otherwise, we move to the right subtree of the current node.
class Solution {
public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
k--;
if (k == 0) return current.val;
current = current.right;
}
return -1;
}
}Follow-up:
If the BST is modified often, we can use a data structure like a balanced BST or a heap to optimize the findKthSmallest routine.
