Find Kth Smallest Element in BST

The kth smallest element in a BST problem requires leveraging the properties of inorder traversal to efficiently locate elements without full sorting, making it a fundamental tree algorithm for FAANG interviews.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. Can we modify the input BST structure, or must we preserve it?
2. What is the expected range of k values (1 to n, or can k be larger)?
3. Are duplicate values allowed in the BST?
4. Should we return the actual node or just the value?
5. What is the target time complexity for follow-up (e.g., O(log n) or O(n))?

Restate the pattern or problem type in your own words: The Kth smallest element in BST problem asks us to find the kth smallest value in a Binary Search Tree without fully traversing and sorting all elements. This leverages the BST property that an in-order traversal produces elements in ascending order.

Clarify the signal words and constraint shape that point to it:

• "kth smallest" or "kth largest" - indicates ordinal selection
• "BST" - suggests we can leverage the ordered structure
• "without full sorting" - hints at leveraging BST properties
• "k is valid" - implies we're looking for a specific rank in the sorted sequence

Note any assumptions you are making:

• The BST is valid (left subtree < node < right subtree)
• k is between 1 and the total number of nodes (inclusive)
• We can use recursion or stack-based traversal
• The input tree structure can be traversed but not necessarily modified

Identify whether the pattern is best suited for static, streaming, or online scenarios: This pattern is best suited for static scenarios where the entire BST is available upfront. It's not ideal for streaming data where elements are continuously added, though it could be adapted for online scenarios with additional tracking structures.

2. When to Use This Pattern

Signal words and constraint shapes:

• "Kth smallest" or "Kth largest" element in a sorted structure
• BST (Binary Search Tree) or tree-like data structure with ordered properties
• "Find the kth element" in a sorted sequence without full sorting
• "Kth element" in a stream or online setting where we can't store all elements

Why this pattern fits better than alternatives: This pattern leverages the BST property where an in-order traversal produces elements in sorted order. Unlike sorting-based approaches (O(n log n)), this pattern uses the inherent ordering structure to achieve O(h) time complexity where h is the height of the tree, making it more efficient for static BSTs.

Conditions where variations apply:

• For streaming data, we might use a min-heap or max-heap approach with size-k tracking
• For arrays, we might use quickselect (O(n) average) instead of BST traversal
• When we need to handle duplicates differently, we may track counts in nodes

Core insight: The key insight is that in-order traversal of a BST visits elements in ascending order, so we can count nodes during traversal to find the kth element without storing all elements. This is more efficient than full sorting or maintaining a complete list of elements.

The pattern works best when we have a BST structure with ordered properties and need to find ordinal statistics without full data reconstruction.

3. Approach Evolution

Interview communication script:

My first instinct is to do an in-order traversal and collect all elements, then return the kth element. But that's O(n) time and O(n) space because I'm storing all elements. That's not optimal.

Let me think about how to optimize this. I notice that in-order traversal of a BST gives elements in sorted order, so I could stop once I've found the kth element. But I still need to traverse all nodes in worst case.

Wait, I can do better with a modified in-order traversal that keeps track of the count. If I maintain a counter and stop when it reaches k, I can avoid storing all elements. That's O(n) time but O(h) space where h is height, which is better than O(n) space.

Actually, let me think about this more carefully. I don't need to store all elements - I can do iterative in-order traversal with a stack, and just count nodes as I visit them. When the count equals k, I return that node's value.

Even better - I can use the property that in-order traversal visits nodes in ascending order. So if I do a recursive in-order traversal and keep a counter, once the counter reaches k, I've found my answer.

The key insight is that I don't need to collect all elements - I just need to find the kth element in sorted order. Since BSTs have the property that in-order traversal gives sorted elements, I can stop early once I've found the kth one.

Brute-force approach and why it is not ideal:

The brute force approach would be to perform an in-order traversal of the BST and store all elements in a list or array. Then return the element at index k-1 (0-indexed). This approach has O(n) time complexity to traverse all nodes and O(n) space complexity to store all elements. This is inefficient because:

1. We're doing unnecessary work by storing all elements when we only need one
2. The space usage is linear in the number of nodes, which can be very large
3. We're not leveraging the BST property that in-order traversal gives sorted elements

Improved approach and the key optimization:

The improved approach uses the BST property that in-order traversal visits elements in ascending order. Instead of collecting all elements, we can:

1. Perform iterative in-order traversal using a stack
2. Keep a counter to track how many nodes we've visited
3. When the counter reaches k, return the current node's value
4. This uses O(h) space where h is the height of the tree (better than O(n))
5. Time complexity remains O(n) in worst case but can be better in practice

The key optimization is that we stop traversal once we've found the kth element, rather than continuing to traverse all nodes.

Final approach with step-by-step reasoning:

1. Use iterative in-order traversal with a stack to avoid recursion stack overflow
2. Keep a counter starting at 0 to track visited nodes
3. Process nodes in the order: left subtree → current node → right subtree
4. For each node popped from stack, increment counter by 1
5. When counter equals k, return the node's value
6. This works because in-order traversal of BST gives elements in ascending order

Important invariants that must hold:

• Stack always contains nodes in the correct traversal order
• Counter accurately tracks how many nodes have been visited so far
• The kth element we're looking for is the one where counter = k

Alternative approach:

Another approach would be to augment the BST node structure with a count field that stores the number of nodes in the left subtree. This would allow O(log n) lookup time by comparing k with left subtree size, but requires modifying the tree structure which may not be allowed. The iterative approach is better when we can't modify the original tree structure.

4. Data Structure Choice

For finding the Kth smallest element in a BST, I'll use the inherent properties of BSTs combined with a stack-based approach.

Primary Data Structures:

• Stack: Used to simulate the inorder traversal iteratively. This allows us to traverse the BST in ascending order without recursion overhead and maintain only the necessary nodes in memory.
• TreeNode: The standard BST node structure with val, left, and right fields.

Why Each Data Structure Is Needed:

• The stack is essential because it enables us to perform iterative inorder traversal (left → root → right), which naturally visits nodes in ascending order. This is key to finding the Kth smallest element efficiently.
• TreeNode structure provides the necessary node information and links to navigate the tree.

Time and Space Impact:

• Stack: O(h) space where h is the height of the tree (worst case O(n) for skewed trees, average O(log n)). This is optimal for iterative traversal.
• TreeNode: No additional space cost beyond the input structure.

Helper Structure:

• No additional helper structures are needed beyond the stack. The algorithm maintains a simple counter to track how many nodes have been visited, making it clean and efficient.

This approach leverages the BST property that inorder traversal yields elements in sorted order, allowing us to stop once we've found the Kth element without processing the entire tree.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step-by-step.

Example: BST with values [3,1,4,null,null,2] and k=1

    3
   / \
  1   4
     /
    2

Step-by-step execution:

1. Initial call: kthSmallest(root, 1)

   • Current node is 3 (root)
   • Left subtree size = 1 (node 1)
   • Since k=1 and left subtree size = 1, we know the answer is at the root

2. Return: We return node 1 as the kth smallest element

Another example: BST with values [5,3,6,2,4,null,null,1] and k=3

      5
     / \
    3   6
   / \   \
  2   4   null
 /
1

Step-by-step execution:

1. Initial call: kthSmallest(root, 3)

   • Current node is 5 (root)
   • Left subtree size = 3 (nodes 1,2,3)
   • Since k=3 and left subtree size = 3, we know the answer is at the root

2. Return: We return node 5 as the kth smallest element

Edge case handling:

• When k=1, we return the leftmost node (minimum)
• When k equals left subtree size + 1, we return current node
• When k is less than left subtree size, we recurse to left subtree

Why it terminates correctly:

The algorithm maintains the invariant that at each node, we know exactly how many nodes are in the left subtree. By comparing k with this count, we can determine whether to search left or right subtree without missing any elements. Since we're working with a valid BST, this approach always finds the correct kth smallest element.

The recursion will eventually reach a leaf node or a node with no left child, at which point we can return that node's value. The key insight is that we never need to traverse the entire tree - we can eliminate portions of the tree based on size comparisons.

6. Java Solution

/**
 * 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 result;
    private int count;
    
    public int kthSmallest(TreeNode root, int k) {
        count = 0;
        result = -1;
        inorderTraversal(root, k);
        return result;
    }
    
    private void inorderTraversal(TreeNode node, int k) {
        if (node == null || result != -1) {
            return;
        }
        
        // Traverse left subtree
        inorderTraversal(node.left, k);
        
        // Process current node
        count++;
        if (count == k) {
            result = node.val;
            return;
        }
        
        // Traverse right subtree
        inorderTraversal(node.right, k);
    }
}

This solution uses the property that an in-order traversal of a BST visits nodes in ascending order. We maintain a counter to track the number of visited nodes and return the value when we reach the kth node. The early termination when result is found makes it efficient by avoiding unnecessary traversal of the right subtree once we've found our answer.

7. Complexity Analysis

Time Complexity: O(H + k) where H is the height of the tree and k is the target rank

The algorithm performs two main operations:

1. Finding the kth smallest element using reverse inorder traversal (right → root → left)
2. Early termination when we reach the kth element

In the worst case, we traverse to the leftmost node (O(H) for height), and in the best case where k is small, we only traverse k nodes. Since we stop once we find the kth element, and each node is visited at most once, the actual time complexity is O(H + k).

Space Complexity: O(H) for recursion stack

The space complexity comes from the call stack due to recursive traversal. In the worst case (skewed tree), this becomes O(n) where n is the number of nodes. For a balanced BST, it's O(log n). The auxiliary space for storing the result is O(1) as we only keep track of the current node value.

Why these bounds are correct:

• Time: The traversal visits nodes in reverse inorder sequence. We stop once we've found the kth element, so we never process more than k nodes after reaching the target. The initial descent to find the leftmost node is O(H) in height.
• Space: Each recursive call adds a frame to the stack, and the maximum depth is the tree height.

Optimality:

This solution is optimal for the given constraints. We must visit at least O(H) nodes to find the kth smallest element in a BST, and we cannot do better than O(H + k) since we need to traverse the tree in-order to find the element. The solution is near-optimal as it's linear in the effective input size (height + rank) rather than quadratic or exponential.

The solution avoids unnecessary traversal by leveraging BST properties and early termination, making it efficient for practical use cases where k << n.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty BST: If root is null, the problem should handle this gracefully (typically with an exception or special return value)
• Single node: When the tree has only one node, k=1 should return that node's value
• k = 1: The smallest element is the leftmost node in the tree

Duplicate Values and Repeated States

• Duplicate values: The problem assumes BST property where duplicates are typically stored in right subtrees, but the solution should work regardless of how duplicates are handled
• k > total nodes: Should handle invalid k values appropriately (e.g., throw exception or return null)

Boundary Conditions

• k = 0: Should be handled as invalid input (1-indexed, so k must be ≥ 1)
• k = total nodes: Should return the largest element (rightmost node)
• k > total nodes: May cause IndexOutOfBoundsException or similar error

Common Implementation Mistakes

• Incorrect inorder traversal: Not properly maintaining the count or not resetting it between recursive calls
• Off-by-one errors: Miscounting nodes or using 0-indexed vs 1-indexed logic inconsistently
• Not handling null nodes: Failing to check for null before accessing node properties
• State persistence issues: Not properly tracking the count across recursive calls or maintaining proper invariants

Implementation-specific Pitfalls

• Stack overflow: For very deep trees, recursive approach may cause stack overflow; iterative approach with explicit stack is safer
• Incorrect termination condition: Not properly stopping when kth element is found
• Memory leaks: Not properly managing stack frames in recursive solutions

// Example of handling edge cases:
if (root == null || k <= 0) {
    throw new IllegalArgumentException("Invalid input");
}

9. Alternative Approaches

There are several alternative approaches to finding the Kth smallest element in a BST, each with different trade-offs:

1. In-order Traversal with Early Termination Instead of collecting all elements, we can perform in-order traversal and stop as soon as we've found the Kth element. This approach uses a counter to track visited nodes and returns immediately when kth node is reached.

public int kthSmallest(TreeNode root, int k) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    int count = 0;
    
    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        
        current = stack.pop();
        count++;
        
        if (count == k) {
            return current.val;
        }
        
        current = current.right;
    }
    
    return -1; // Should never reach here for valid input
}

2. Morris Traversal (O(1) Space) This approach modifies the tree temporarily to create threads, allowing in-order traversal without a stack. It's useful when we want to avoid O(h) space usage where h is height of tree.

3. Augmented BST with Size Tracking If we can modify the tree structure, we can augment each node to store the size of its left subtree. This allows O(h) time lookup where h is height, without needing to traverse all nodes.

Trade-offs:

• The stack-based approach is most readable and handles edge cases cleanly
• Morris traversal saves space but modifies tree structure temporarily
• Augmented BST is optimal for multiple queries but requires structural changes
• The stack-based solution is preferred in interviews due to clarity and maintainability

The chosen solution (stack-based in-order traversal) is preferred because it's clean, readable, and handles all edge cases properly while maintaining O(h) space complexity where h is the height of the tree.

10. Test Cases

// Test case 1: Basic valid BST with k=3
//       5
//      / \
//     3   7
//    / \ / \
//   2  4 6  8
// k=3 should return 4 (in-order: 2,3,4,5,6,7,8)
TreeNode root1 = new TreeNode(5);
root1.left = new TreeNode(3);
root1.right = new TreeNode(7);
root1.left.left = new TreeNode(2);
root1.left.right = new TreeNode(4);
root1.right.left = new TreeNode(6);
root1.right.right = new TreeNode(8);
// Expected: 4

// Test case 2: k=1 (smallest element)
//       5
//      / \
//     3   7
//    / \ / \
//   2  4 6  8
// k=1 should return 2
// Expected: 2

// Test case 3: k equals tree size
//       5
//      / \
//     3   7
//    / \ / \
//   2  4 6  8
// k=7 should return 8
// Expected: 8

// Test case 4: Single node tree
TreeNode root4 = new TreeNode(1);
// k=1 should return 1
// Expected: 1

// Test case 5: Duplicate values (if allowed)
//       5
//      / \
//     5   7
//    / \ / \
//   3  5 6  8
// k=4 should return 5 (in-order: 3,5,5,5,6,7,8)
// Expected: 5

The test cases cover:

• Basic valid BST structure with typical in-order traversal
• Edge case where k=1 (minimum element)
• Edge case where k equals total nodes (maximum element)
• Minimal valid input (single node)
• Duplicate values handling (if duplicates are allowed in the problem)

Each test case validates a different aspect of the algorithm's correctness and boundary condition handling.

11. Final Summary

The core idea is to leverage the in-order traversal property of BSTs to efficiently find the kth smallest element using iterative DFS with a stack, achieving O(H + k) time complexity where H is the tree height. This approach works because in-order traversal naturally visits nodes in ascending order, and we can stop early once we've found the kth element. The solution is optimal for static BSTs and handles all edge cases gracefully, making it a robust choice for production systems.