Problem Statement

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

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

Constraints:

• The number of nodes in the tree is n.
• 1 <= k <= n <= 10^4
• 0 <= Node.val <= 10^4

---

Approach in Plain English

1. In a BST, the inorder traversal (left → root → right) gives the nodes in sorted order.
2. So, we can do inorder traversal and keep track of the number of nodes visited.
3. When we have visited k nodes, the current node is the kth smallest.
4. This approach is efficient because we don’t need to store all nodes in an array—just a counter.

Key idea: Inorder traversal of BST produces sorted elements.

---

Beginner-Friendly Dry Run

Take BST:

       3
      / \
     1   4
      \
       2

k = 1

1. Start inorder traversal at root = 3.
2. Go left → node = 1
   • Go left → null → return
   • Visit node 1 → count = 1 → count == k → return 1

kth smallest = 1

Another example: k = 3

• Inorder traversal sequence: 1 → 2 → 3 → 4
• Third node visited = 3 → answer = 3

---

Textual Approach

1. Initialize counter count = 0.
2. Perform inorder traversal recursively:
   • Traverse left subtree
   • Increment count → if count == k, store result
   • Traverse right subtree
3. Return the stored result once k nodes have been visited.

Optional: Can also do iterative inorder traversal using a stack for large trees.

---

Java Code (Recursive)

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

public class KthSmallestInBST {

    private int count = 0;
    private int result = 0;

    public int kthSmallest(TreeNode root, int k) {
        inorder(root, k);
        return result;
    }

    private void inorder(TreeNode node, int k) {
        if (node == null) return;

        inorder(node.left, k);

        count++;
        if (count == k) {
            result = node.val;
            return;
        }

        inorder(node.right, k);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(1);
        root.right = new TreeNode(4);
        root.left.right = new TreeNode(2);

        KthSmallestInBST solver = new KthSmallestInBST();
        System.out.println(solver.kthSmallest(root, 1)); // Output: 1
        System.out.println(solver.kthSmallest(root, 3)); // Output: 3
    }
}

---

Java Code (Iterative Using Stack)

import java.util.Stack;

public class KthSmallestBSTIterative {

    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;

        while (current != null || !stack.isEmpty()) {
            // Go to the leftmost node
            while (current != null) {
                stack.push(current);
                current = current.left;
            }

            current = stack.pop();
            k--;
            if (k == 0) return current.val;

            current = current.right;
        }

        return -1; // k is invalid
    }
}

---

Key Points

• Inorder traversal of BST gives nodes in sorted order.
• Recursive or iterative traversal works.
• Time Complexity: O(H + k) where H = tree height (recursive call stack or path to leftmost)
• Space Complexity: O(H) due to recursion stack or stack for iterative version.
• Very efficient because we don’t need to traverse the entire tree if k is small.