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.

Additional information

• The number of nodes in the tree is n.
• 1 <= k <= n <= 10^4
• 0 <= Node.val <= 10^4

Example 1:

Input: root = [3, 1, 4, null, 2], k = 1

Output: 1

Example 2:

Input: root = [5, 3, 6, 2, 4, null, null, 1], k = 3

Output: 3

Explanation: The inorder traversal of the tree is [1, 2, 3, 4, 5, 6]. The 3rd smallest element is 3.

Iterative Inorder Traversal - Optimal

Intuition

The core property of a Binary Search Tree (BST) is that an Inorder Traversal (Left -> Node -> Right) visits the nodes in strictly ascending sorted order.

Instead of traversing the entire tree and storing all the values in an array (which would take O(n) time and space), we can perform an iterative inorder traversal and simply keep a counter. The moment our counter reaches k, we know we are currently standing on the kth smallest element, and we can stop the search immediately.

Algorithm

1. Initialize an empty stack.
2. Set a curr pointer to root.
3. Loop while curr is not None or the stack is not empty:

• Go Left: While curr is not None, push curr onto the stack and move curr = curr.left. This drills down to the smallest available element.
• Process Node: Pop a node from the stack. This is the next smallest element in the sequence.
• Decrement k.
• If k == 0, we have found our target! Return the popped node's value.
• Go Right: Move curr = node.right to explore the next largest values.

def kth_smallest(root: Optional[TreeNode], k: int) -> int:
    stack = []
    curr = root
    
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
            
        curr = stack.pop()
        k -= 1
        
        if k == 0:
            return curr.val
            
        curr = curr.right
        
    return -1 # Should not be reached given valid constraints

Time & Space Complexity

• Time complexity: O(H + k)

• Reason: We first traverse down to the leftmost leaf, which takes O(H) time where H is the height of the tree. Then we process k nodes. In the worst case (skewed tree), this could be O(n), but for a balanced tree it is O(log n + k).

• Space complexity: O(H)

• Reason: The space complexity is determined by the size of the stack. In the worst case, the stack stores H nodes, corresponding to the height of the tree.

Recursive Inorder Traversal

Intuition

We can also use recursion to perform the inorder traversal. We need a way to keep track of our target k and the final result across the recursive calls. We can achieve this by passing an array or an object, or simply by using class-level variables (or nonlocal variables in a nested Python function).

Algorithm

1. Initialize an array res = [] to store the inorder traversal, OR use a counter variable. For simplicity and clarity in interviews, passing a mutable list to store the target is very Pythonic. Let's use count and result variables.
2. Create a nested helper function inorder(node):

• If node is None, return.
• Call inorder(node.left).
• Decrement k. If k == 0, set result to node.val and return.
• If result is already found (not None), return early to save time.
• Call inorder(node.right).

3. Call inorder(root) and return the found result.

def kth_smallest(root: Optional[TreeNode], k: int) -> int:
    res = None
    
    def inorder(node):
        nonlocal k, res
        if not node or res is not None:
            return
            
        inorder(node.left)
        
        k -= 1
        if k == 0:
            res = node.val
            return
            
        inorder(node.right)
        
    inorder(root)
    return res

Time & Space Complexity

• Time complexity: O(H + k)

• Reason: We stop searching as soon as we find the kth element, so we process at most H + k nodes.

• Space complexity: O(H)

• Reason: The recursion stack depth is limited to the height H of the tree.