This is a fundamental interview question that tests your understanding of BST properties and tree traversal algorithms.

Brute Force Approach for Kth Smallest Element in a BST

A naive approach to solving the Kth Smallest Element in a BST involves ignoring the specific structural properties of the BST and treating it as a generic binary tree.

1. Traverse and Collect: Perform any standard traversal (Preorder, Inorder, or Postorder) of the entire tree.
2. Store: Store every node's value in a dynamic array or list.
3. Sort: Sort the list of values in ascending order.
4. Select: Return the element at index k-1.

Pseudo-code:

text
function bruteForce(root, k):
    list = []
    traverse(root, list) // adds all nodes to list
    sort(list)
    return list[k-1]

Complexity Analysis:

• Time Complexity: $O(N \log N)$. While the traversal takes $O(N)$, sorting the list of values dominates the complexity.
• Space Complexity: $O(N)$ to store all node values in the list.

Why it fails: While this approach produces the correct answer, it is computationally inefficient. It fails to utilize the inherent sorted property of the Binary Search Tree. Furthermore, storing all $N$ elements is unnecessary when we only need the $k$-th element, leading to suboptimal space usage.

Core Insight for Kth Smallest Element in a BST

The key intuition for the optimal solution lies in the relationship between the BST property and Inorder Traversal.

In a BST:

1. Left Subtree: Contains values $< \text{Root}$.
2. Root: Contains the middle value relative to its subtrees.
3. Right Subtree: Contains values $> \text{Root}$.

When we execute a recursive inorder traversal, the algorithm prioritizes the left child. It dives as deep as possible into the left subtree before processing a node. This means the very first node "processed" (or visited) by the inorder logic is the minimum element in the tree. The second node processed is the second smallest, and so on.

Instead of storing values, we can maintain a counter. As the recursion unwinds from the left, we increment our count of visited nodes. When the count equals $k$, the current node is our answer.

Visual Description: Visualize the recursion stack growing as the algorithm traverses down to the leftmost leaf. At this point, the stack depth is equal to the height of the tree. The algorithm hits a null left child and returns to the leaf node. This leaf is the "1st smallest." The algorithm then attempts to go right. If no right child exists, it pops the stack to the parent, which becomes the "2nd smallest." This sequence strictly follows the numerical order of the values.

Algorithm Strategy: Tree DFS - Recursive Inorder Traversal

To implement this efficiently, we use a Depth-First Search (DFS) strategy specifically following the Inorder scheme.

1. Global/Class State: Maintain a counter (initialized to $k$) and a variable to store the result. Alternatively, pass the counter by reference.
2. Recursive Step (Left): Recursively call the function on the left child. This ensures we process smaller numbers first.
3. Process Node:
   • After returning from the left child, we are at the current smallest available node.
   • Decrement the counter $k$.
   • Check if $k == 0$. If true, record the current node's value as the result. We can optionally set a flag or return early to stop further processing.
4. Recursive Step (Right): If the result hasn't been found yet, recursively call the function on the right child.

This approach ensures we only visit the necessary nodes. Once the $k$-th element is found, the remaining traversal is skipped (or effectively ignored).

Execution Flow

Let's trace the execution for root = [5,3,6,2,4], k = 3.

1. Start DFS(5): Call DFS(5.left) $\to$ DFS(3).
2. At Node 3: Call DFS(3.left) $\to$ DFS(2).
3. At Node 2: Call DFS(2.left) $\to$ DFS(null). Returns.
4. Process Node 2: Decrement $k$. $k$ becomes 2. Check $k=0$? No.
5. At Node 2: Call DFS(2.right) $\to$ DFS(null). Returns. Node 2 function completes.
6. Back at Node 3: We returned from the left child.
7. Process Node 3: Decrement $k$. $k$ becomes 1. Check $k=0$? No.
8. At Node 3: Call DFS(3.right) $\to$ DFS(4).
9. At Node 4: Call DFS(4.left) $\to$ DFS(null). Returns.
10. Process Node 4: Decrement $k$. $k$ becomes 0. Check $k=0$? Yes.
11. Result Found: Store 4 as the answer. Stop recursion.

Proof of Correctness

The correctness relies on the fundamental theorem of Binary Search Trees: an inorder traversal of a BST yields the keys in monotonically increasing order.

1. Base Case: The leftmost node in a BST is the minimum. The inorder traversal visits this node first.
2. Inductive Step: Assuming the traversal has visited $i$ nodes in correct sorted order, the logic of inorder traversal (finish left subtree, visit root, start right subtree) guarantees the $(i+1)$-th node visited is the immediate successor of the $i$-th node.
3. Conclusion: By decrementing $k$ at each visit, when $k$ reaches 0, the current node is strictly the $k$-th node in the sorted sequence.

Reference Implementation

C++ Solution for LeetCode 230

cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        int result = -1;
        inorder(root, k, result);
        return result;
    }

private:
    // Standard Inorder Traversal: Left -> Root -> Right
    void inorder(TreeNode* node, int& k, int& result) {
        if (!node) return;
        
        // Traverse left subtree
        inorder(node->left, k, result);
        
        // Process current node
        k--;
        if (k == 0) {
            result = node->val;
            return;
        }
        
        // Optimization: stop if result is already found
        if (result != -1) return;
        
        // Traverse right subtree
        inorder(node->right, k, result);
    }
};

Java Solution for LeetCode 230

java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int count;
    private int result;

    public int kthSmallest(TreeNode root, int k) {
        count = k;
        result = -1;
        inorder(root);
        return result;
    }

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

        // Traverse left
        inorder(node.left);

        // Process current node
        count--;
        if (count == 0) {
            result = node.val;
            return; // Found the kth element
        }
        
        // Early exit optimization
        if (result != -1) return;

        // Traverse right
        inorder(node.right);
    }
}

Python Solution for LeetCode 230

python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        self.k = k
        self.result = None
        
        def inorder(node):
            if not node or self.result is not None:
                return
            
            # Traverse Left
            inorder(node.left)
            
            # Process Node
            self.k -= 1
            if self.k == 0:
                self.result = node.val
                return
            
            # Traverse Right
            inorder(node.right)
            
        inorder(root)
        return self.result