Problem Description

You are given the root of a binary search tree (BST) and an integer k. Your task is to find and return the kth smallest value among all node values in the tree.

The important details to understand:

• The tree is a binary search tree, meaning for any node, all values in its left subtree are smaller than the node's value, and all values in its right subtree are larger
• The counting is 1-indexed, so k=1 means finding the smallest value, k=2 means finding the second smallest value, and so on
• You need to return the actual value (not the node) that is the kth smallest

For example, if you have a BST with values [1, 2, 3, 4, 5] and k=3, you would return 3 as it's the third smallest value in the tree.

The solution uses an iterative in-order traversal approach with a stack. In-order traversal of a BST naturally visits nodes in ascending order of their values. The algorithm:

1. Traverses to the leftmost node (smallest value) by pushing nodes onto a stack
2. Pops nodes from the stack one by one (visiting them in ascending order)
3. Decrements k for each visited node
4. When k reaches 0, returns the current node's value as it's the kth smallest
5. After visiting a node, moves to its right subtree to continue the in-order pattern

This approach has O(h + k) time complexity where h is the height of the tree, and O(h) space complexity for the stack.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary search tree is a special type of graph where each node has at most two children (left and right). Trees are a subset of graphs with no cycles and a hierarchical structure.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary search tree (BST), which is a specialized tree data structure.

DFS

• We arrive at DFS (Depth-First Search): For tree problems, DFS is a natural choice. In this specific problem, we need to traverse the BST in a way that visits nodes in sorted order to find the kth smallest element.

Conclusion: The flowchart suggests using DFS for this problem. The solution implements an iterative DFS approach using a stack to perform an in-order traversal. In-order traversal of a BST visits nodes in ascending order of their values, which is perfect for finding the kth smallest element. The algorithm traverses left as far as possible (going deep first), then processes nodes in sorted order, counting down from k until we reach the desired element.

Intuition

The key insight comes from understanding a fundamental property of binary search trees: an in-order traversal visits nodes in ascending order. Since we need the kth smallest element, we can leverage this property instead of collecting all values and sorting them.

Think about how in-order traversal works: we visit the left subtree first (which contains smaller values), then the current node, then the right subtree (which contains larger values). This naturally gives us values in sorted order.

Instead of traversing the entire tree and storing all values, we can optimize by counting as we traverse. Each time we visit a node during in-order traversal, we know it's the next smallest unvisited value. So we can maintain a counter that decrements with each node visit. When our counter reaches 0, we've found our kth smallest element.

The iterative approach with a stack mimics the recursive in-order traversal but gives us more control. We push nodes onto the stack as we go left (finding smaller values), then pop and process them one by one. This way, we can stop immediately when we find the kth element rather than continuing the traversal.

The beauty of this solution is that we don't need extra space to store all values, and we can potentially stop early without visiting all nodes. If k is small relative to the tree size, we only need to visit approximately k nodes plus the path to get to the smallest node, making it very efficient.

Solution Approach

The solution implements an iterative in-order traversal using a stack data structure. Let's walk through the implementation step by step:

Data Structure Used: A stack (stk) to keep track of nodes as we traverse down the left path of the tree.

Algorithm Steps:

1. Initialize an empty stack to store nodes during traversal.

2. Main traversal loop - Continue while either root is not None or the stack is not empty:

   while root or stk:

3. Go left as far as possible - When root exists, push it onto the stack and move to its left child:

   if root:
       stk.append(root)
       root = root.left

   This ensures we reach the smallest unvisited node first.

4. Process the next smallest node - When we can't go left anymore (root is None):

   else:
       root = stk.pop()
       k -= 1

   Pop a node from the stack (this is the next smallest unvisited node) and decrement k.

5. Check if we found the kth element:

   if k == 0:
       return root.val

   When k reaches 0, we've found our answer and return immediately.

6. Move to the right subtree:

   root = root.right

   After processing a node, explore its right subtree (which contains values larger than the current node but smaller than its ancestors).

Why This Works:

• The stack maintains nodes in a path from root to the current position
• Popping from the stack gives us nodes in ascending order of their values
• By counting down from k, we know exactly when we've reached the kth smallest element
• The algorithm naturally handles both balanced and unbalanced trees efficiently

Time Complexity: O(H + k) where H is the height of the tree. In the worst case, we need to go down to the leftmost leaf (H operations) and then visit k nodes.

Space Complexity: O(H) for the stack, which in the worst case stores a path from root to leaf.

Example Walkthrough

Let's walk through finding the 3rd smallest element in this BST:

       5
      / \
     3   7
    / \   \
   1   4   9

Target: Find k=3 (third smallest value)

Step-by-step execution:

Initial State: k=3, root=5, stk=[]

Step 1-3: Go left until we can't

• Current: root=5, push to stack → stk=[5], go left → root=3
• Current: root=3, push to stack → stk=[5,3], go left → root=1
• Current: root=1, push to stack → stk=[5,3,1], go left → root=None

Step 4: Process first node (smallest)

• Since root=None, pop from stack → root=1, stk=[5,3]
• Decrement k → k=2
• Check: k≠0, continue
• Move right → root=None (node 1 has no right child)

Step 5: Process second node

• Since root=None, pop from stack → root=3, stk=[5]
• Decrement k → k=1
• Check: k≠0, continue
• Move right → root=4

Step 6: Push node 4

• Current: root=4, push to stack → stk=[5,4], go left → root=None

Step 7: Process third node

• Since root=None, pop from stack → root=4, stk=[5]
• Decrement k → k=0
• Check: k=0, FOUND! Return 4

Result: The 3rd smallest value is 4

Key Observations:

• We visited nodes in order: 1 → 3 → 4, which are indeed the smallest, 2nd smallest, and 3rd smallest values
• The stack helped us backtrack from node 1 to node 3, then from node 4 to potentially node 5
• We stopped immediately upon finding the 3rd element, without needing to visit nodes 5, 7, or 9
• The stack at its maximum held 3 nodes ([5,3,1]), which corresponds to the height of the left path

Solution Implementation

Time and Space Complexity

Time Complexity: O(H + k) where H is the height of the tree.

The algorithm performs an in-order traversal using an iterative approach with a stack. In the worst case, we need to:

• First traverse down to the leftmost node, which takes O(H) time
• Then visit k nodes in in-order sequence to find the kth smallest element

Since we stop as soon as we find the kth element, we don't necessarily traverse the entire tree. The total operations are bounded by O(H + k).

Space Complexity: O(H) where H is the height of the tree.

The space is used by the stack to store nodes during the traversal. In the worst case:

• For a skewed tree (essentially a linked list), the height H = N, so space complexity becomes O(N)
• For a balanced tree, the height H = log(N), so space complexity becomes O(log N)

The stack will contain at most H nodes at any point during the traversal, as it stores the path from the current node back to the root along the left spine of the tree.

Common Pitfalls

1. Forgetting to Handle the Right Subtree

A common mistake is forgetting to set current_node = current_node.right after processing a node. This causes an infinite loop because the algorithm keeps popping the same nodes without progressing through the tree.

Incorrect Implementation:

while current_node or stack:
    if current_node:
        stack.append(current_node)
        current_node = current_node.left
    else:
        current_node = stack.pop()
        k -= 1
        if k == 0:
            return current_node.val
        # MISSING: current_node = current_node.right

Solution: Always remember to move to the right subtree after processing a node to maintain the in-order traversal pattern.

2. Using Recursion with Large Trees (Stack Overflow Risk)

While recursive in-order traversal is simpler to write, it can cause stack overflow for very deep trees.

Risky Recursive Approach:

def kthSmallest(self, root, k):
    self.k = k
    self.result = None
  
    def inorder(node):
        if not node or self.result is not None:
            return
        inorder(node.left)
        self.k -= 1
        if self.k == 0:
            self.result = node.val
            return
        inorder(node.right)
  
    inorder(root)
    return self.result

Solution: Use the iterative approach with an explicit stack as shown in the main solution to avoid recursion depth limitations.

3. Modifying k Directly in Helper Functions

When using helper functions, directly modifying the parameter k won't work as expected due to Python's pass-by-value for integers.

Incorrect Implementation:

def kthSmallest(self, root, k):
    def helper(node, k):  # k is a local copy
        # ... traversal logic ...
        k -= 1  # This doesn't affect the outer k
        if k == 0:
            return node.val

Solution: Either use a mutable container (like a list [k]) or use instance variables (self.k) to maintain state across function calls, or stick with the iterative approach.

4. Not Checking for Empty Tree or Invalid k

The solution assumes valid input, but in production code, you might want to handle edge cases.

More Robust Implementation:

def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
    if not root:
        raise ValueError("Tree is empty")
  
    stack = []
    current_node = root
    nodes_visited = 0
  
    while current_node or stack:
        if current_node:
            stack.append(current_node)
            current_node = current_node.left
        else:
            current_node = stack.pop()
            nodes_visited += 1
            k -= 1
          
            if k == 0:
                return current_node.val
          
            current_node = current_node.right
  
    # If we exit the loop, k was larger than the number of nodes
    raise ValueError(f"k={k+nodes_visited} is larger than tree size")