AlgoMaster Logo

Kth Smallest Element in a BST

tree=[3, 1, 4, null, 2],k=1
1public int kthSmallest(TreeNode root, int k) {
2    Stack<TreeNode> stack = new Stack<>();
3    TreeNode current = root;
4
5    while (current != null || !stack.isEmpty()) {
6        // Go to leftmost node
7        while (current != null) {
8            stack.push(current);
9            current = current.left;
10        }
11
12        // Visit node
13        current = stack.pop();
14        k--;
15        if (k == 0) {
16            return current.val;
17        }
18
19        // Move to right subtree
20        current = current.right;
21    }
22
23    return -1;
24}
0 / 13
k: 1R3142Stack