Domain 2MediumCORE

Kth Smallest Element in a BST

We are given the root of a Binary Search Tree (BST) and an integer k. Our goal is to find the value of the node that represents the kth smallest element in the tree. The input guarantees 1 <= k <= n, where n is the total number of nodes, so we don't need to handle invalid k values like 0 or greater than n.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Binary Search#Tree

230. Kth Smallest Element in a BST

Model: qwen3.5:9b
Topics: Binary Search,Tree
FAANG asked: 1
Acceptance rate: 62.9%


Problem Breakdown

We are given the root of a Binary Search Tree (BST) and an integer k. Our goal is to find the value of the node that represents the kth smallest element in the tree. The input guarantees 1 <= k <= n, where n is the total number of nodes, so we don’t need to handle invalid k values like 0 or greater than n.

Key constraints and properties:

  • BST Property: For any node, all left descendants are smaller, and all right descendants are larger. This implies an in-order traversal (Left -> Root -> Right) visits nodes in strictly ascending order of their values.
  • Input Format: Standard LeetCode TreeNode structure (val, left, right).
  • Edge Cases to Consider: A tree with only one node, a skewed tree (worst-case height), and finding the minimum or maximum element (k=1 vs k=n).

Intuition

A brute-force approach would be to perform an in-order traversal of the entire tree, store all values in a list, sort them if necessary (though BST guarantees order naturally), and then pick the k-1 index. This takes O(N) time but requires O(N) extra space for storage before we even find the answer.

However, since it’s a BST, we don’t need to store all elements or wait until the end of traversal. We can stop exactly when we reach our target count. The core insight is that in-order traversal yields sorted values. Therefore, if we maintain a counter during an in-order walk and increment it every time we visit a node’s value (specifically after visiting its left subtree), the moment this counter equals k, we have found our answer.

Follow-up Optimization: If updates are frequent, maintaining simple BST structure isn’t enough because finding the kth element would require traversing O(N) in worst case per query. To optimize for frequent insert/delete and queries, one might use an Order Statistic Tree. This involves augmenting each node with a size field representing the number of nodes in its left subtree (including itself). With this augmentation:

  1. We can calculate how many elements are smaller than current root by looking at left.size.
  2. If k <= left.size, go left; if k == left.size + 1, we found it; otherwise, subtract from k and go right. This allows O(log N) query time without full traversal.

Approach

I will implement an iterative in-order traversal using a stack. I prefer this over recursion for two reasons:

  1. It avoids Python’s default recursion limit issues (which would crash on deep/skewed trees with N=104N=10^4).
  2. It gives explicit control to stop immediately once k is found, preventing unnecessary traversal of the rest of the tree if we find a match early in the sorted sequence.

The algorithm proceeds as follows:

  1. Initialize an empty stack and push all left children starting from root until null (this simulates going down the “left spine”).
  2. Pop nodes one by one, incrementing our counter count each time we process a node’s value.
  3. If count == k, return the current node’s value immediately.
  4. After processing a node, push its right child onto the stack and repeat step 1 (push left children of that new branch).

Complexity Analysis

  • Time Complexity: O(H), where H is the height of the tree. In the worst case (skewed BST like a linked list), H = N, so it’s O(N). In a balanced BST, H = log N. Since we stop early upon finding k, this is generally faster than traversing all nodes unless k is near n.
  • Space Complexity: O(H) for the stack used in iterative traversal to store path from root to current node.

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def kthSmallest(root: 'TreeNode', k: int) -> int:
    stack = []
    current = root
    
    # Iterative in-order traversal to find the k-th smallest element
    while True:
        if current is not None:
            # Go as far left as possible, pushing nodes onto stack
            stack.append(current)
            current = current.left
        
        elif len(stack) > 0:
            # Pop node from stack (this simulates returning up the tree)
            current = stack.pop()
            
            # Increment count and check if we found our target
            k -= 1
            if k == 0:
                return current.val
            
            # Move to right subtree after processing left side of this node
            current = current.right
        
        else:
            break
    
    return -1 # Should not reach here given constraints (k <= n)

Edge Cases Handled

  • Single Node Tree: The loop pushes root, pops it immediately. k decrements to 0 on first pop if k=1, returning the node’s value correctly.
  • Skewed BST (Linked List): Iterative approach handles deep trees without hitting recursion depth limits (RecursionError).
  • Finding Minimum Element: If k=1, we traverse all left children, then process root immediately after popping stack, decrementing k to 0 and returning. This is the most efficient path for minimum value (O(H)).
  • Empty Tree Constraints: The problem constraints state n≥kn \ge k, so an empty tree or invalid k are not possible inputs per specification; however, if they were, a check at start would be added before entering loop.