Kth Smallest Element in a BST

LeetCode 230: Kth Smallest Element in a BST Solution & Explanation

Problem Overview

TL;DR: Perform a recursive inorder traversal to visit nodes in strictly ascending order, decrementing a counter k until it reaches zero to identify the target value.

The LeetCode 230 problem, "Kth Smallest Element in a BST," asks us to find the $k$-th smallest value within a Binary Search Tree (BST). Given the root of the tree and an integer $k$, we must return the value of the node that would appear at the $k$-th position (1-indexed) if all nodes were sorted by value.

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:

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.

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.

Pattern Reuse Notes

The Tree DFS - Recursive Inorder Traversal pattern is versatile and appears in several other popular interview questions:

• LeetCode 94: Binary Tree Inorder Traversal - The foundational problem for this pattern.
• LeetCode 98: Validate Binary Search Tree - Uses inorder traversal to verify that the previous node is always smaller than the current node.
• LeetCode 173: Binary Search Tree Iterator - Implements a controlled, iterative version of this pattern.
• LeetCode 501: Find Mode in Binary Search Tree - Uses the sorted property of inorder traversal to count frequency of adjacent identical values.

Mastering this pattern allows you to solve almost any BST problem that involves order or sorting.

Reference Implementation

C++ Solution for LeetCode 230

1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    int kthSmallest(TreeNode* root, int k) {
15        int result = -1;
16        inorder(root, k, result);
17        return result;
18    }
19
20private:
21    // Standard Inorder Traversal: Left -> Root -> Right
22    void inorder(TreeNode* node, int& k, int& result) {
23        if (!node) return;
24        
25        // Traverse left subtree
26        inorder(node->left, k, result);
27        
28        // Process current node
29        k--;
30        if (k == 0) {
31            result = node->val;
32            return;
33        }
34        
35        // Optimization: stop if result is already found
36        if (result != -1) return;
37        
38        // Traverse right subtree
39        inorder(node->right, k, result);
40    }
41};

Java Solution for LeetCode 230

1/**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 *     int val;
5 *     TreeNode left;
6 *     TreeNode right;
7 *     TreeNode() {}
8 *     TreeNode(int val) { this.val = val; }
9 *     TreeNode(int val, TreeNode left, TreeNode right) {
10 *         this.val = val;
11 *         this.left = left;
12 *         this.right = right;
13 *     }
14 * }
15 */
16class Solution {
17    private int count;
18    private int result;
19
20    public int kthSmallest(TreeNode root, int k) {
21        count = k;
22        result = -1;
23        inorder(root);
24        return result;
25    }
26
27    private void inorder(TreeNode node) {
28        if (node == null) return;
29
30        // Traverse left
31        inorder(node.left);
32
33        // Process current node
34        count--;
35        if (count == 0) {
36            result = node.val;
37            return; // Found the kth element
38        }
39        
40        // Early exit optimization
41        if (result != -1) return;
42
43        // Traverse right
44        inorder(node.right);
45    }
46}

Python Solution for LeetCode 230

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7
8class Solution:
9    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
10        self.k = k
11        self.result = None
12        
13        def inorder(node):
14            if not node or self.result is not None:
15                return
16            
17            # Traverse Left
18            inorder(node.left)
19            
20            # Process Node
21            self.k -= 1
22            if self.k == 0:
23                self.result = node.val
24                return
25            
26            # Traverse Right
27            inorder(node.right)
28            
29        inorder(root)
30        return self.result