Kth Smallest Element in a BST | Leetcode 230

Welcome to our deep dive on Kth Smallest Element in a BST (Leetcode 230). This exploits a core property of Binary Search Trees.

Problem Statement

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

Example: root = [3,1,4,null,2], k = 1 => Output: 1

Approach: Iterative In-Order Traversal O(N)

The absolute most important property of any Binary Search Tree is that executing an In-Order Traversal will visit the node values in strictly ascending sorted order. Because of this, the k-th node we visit during an In-Order traversal is guaranteed to be the k-th smallest element in the entire tree!

1. Use an explicit Stack.
2. Traverse as far left as mathematically possible, pushing nodes to the stack.
3. Pop a node. This is the next smallest node conceptually.
4. Decrement k. If k == 0, we found our target! Return the node's value.
5. If k > 0, traverse to the right child and repeat.

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = []
        curr = root
        
        while stack or curr:
            while curr:
                stack.append(curr)
                curr = curr.left
                
            curr = stack.pop()
            k -= 1
            if k == 0:
                return curr.val
                
            curr = curr.right

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (230)