Kth Smallest Element in a BST

Given the root of a BST and integer k, return the kth smallest value (1-indexed) of all values in the BST.

Example 1

Input: root=[3,1,4,null,2], k=1 → Output: 1

Example 2

Input: root=[5,3,6,2,4,null,null,1], k=3 → Output: 3

Solution Approach

Inorder traversal of a BST gives values in sorted order. Do iterative inorder traversal and return the kth element visited.

Use iterative inorder with a stack.
Push nodes left as far as possible.
Pop a node, decrement k. If k==0, return node.val.
Move to right subtree.

Java

import java.util.*;

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) { stack.push(cur); cur = cur.left; }
            cur = stack.pop();
            if (--k == 0) return cur.val;
            cur = cur.right;
        }
        return -1;
    }
}

Time Complexity: O(H + k)
Space Complexity: O(H)