230. Kth Smallest Element in a BST 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        // left -> root -> right

        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }

            // now: root is null
            TreeNode node = stack.pop();
            if (--k == 0) {
                return node.val;
            }
            root = node.right; // 注意此处是赋值给 root 而不是 stack.push(node.right)，因为需要将 node.right 作为一颗子树进行递归
        }

        throw new RuntimeException("Cannot find kth smallest node");
    }
}

References

230. Kth Smallest Element in a BST