What pattern does Kth Smallest Element in a BST use?

The Pattern: DFS (Inorder Traversal with Early Termination) The Heuristic: In BSTs, in-order traversal yields sorted values; by simulating recursion with a stack and stopping after visiting k nodes, the algorithm efficiently finds the kth smallest element without traversing the entire tree.

Kth Smallest Element in a BST - LeetCode Solution

Q: What is the time complexity of Kth Smallest Element in a BST?

O(h + k). The algorithm traverses down to the leftmost node (height h) and then visits k nodes in order. Each node is pushed and popped at most once, so the total operations are proportional to h + k.

Problem

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.

The number of nodes in the tree is n.
1 ≤ k ≤ n ≤ 10⁴
0 ≤ Node.val ≤ 10⁴

Example

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

Output: 1

The BST in-order traversal visits nodes in ascending order: [1, 2, 3, 4]. The 1st smallest element is 1. The algorithm uses an iterative in-order traversal with a stack to simulate recursion. It pushes left children until none remain, then processes nodes by popping from the stack, decrementing k each time. When k reaches zero, the current node's value is returned immediately, ensuring O(k) time complexity in the average case.

Approach

Straightforward Solution

A naive approach is to perform a full in-order traversal, collect all node values in a list, and then return the kth element. This requires O(n) time and O(n) space, which is inefficient if k is small.

Core Observation

In a BST, an in-order traversal visits nodes in ascending order of their values. Therefore, the kth node visited during an in-order traversal is the kth smallest element.

Path to Optimal

The key insight is that the traversal can stop as soon as the kth smallest element is found, avoiding unnecessary visits. Using an iterative in-order traversal with a stack allows controlled traversal and early termination. This reduces time complexity to O(k) in the average case and space complexity to O(h), where h is the tree height.

Optimal Approach

Use an iterative in-order traversal with a stack. Push all left children onto the stack until none remain. Then pop the top node, decrement k, and if k is zero, return the node's value. Otherwise, move to the right child and repeat. This approach leverages BST properties and controlled traversal to efficiently find the kth smallest element.

Time

O(h + k)

The algorithm traverses down to the leftmost node (height h) and then visits k nodes in order. Each node is pushed and popped at most once, so the total operations are proportional to h + k.

Space

O(h)

The stack stores nodes along the path from root to the current node, which is at most the height of the tree. This auxiliary space is required for the traversal and is independent of the output.

Solution

1class Solution:
  def kthSmallest(self, root: 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

1class Solution {
  public int kthSmallest(TreeNode root, int k) {
      Deque<TreeNode> stack = new ArrayDeque<>();
      TreeNode curr = root;
5
      while (curr != null || !stack.isEmpty()) {
          while (curr != null) {
              stack.push(curr);
              curr = curr.left;
          }
11
          curr = stack.pop();
          k--;
          if (k == 0) {
              return curr.val;
          }
17
          curr = curr.right;
      }
20
      throw new IllegalArgumentException();
  }
23}

Step-by-Step Solution

1

Initialize Stack and Current Pointer for Traversal

3stack = []
4curr = root
6while stack or curr:

Objective

To set up the data structures needed to perform an iterative in-order traversal of the BST.

Key Insight

Using a stack to simulate recursion allows controlled traversal without the overhead of function calls. The current pointer starts at the root and guides the traversal down the left subtree first, which is essential for in-order traversal to visit nodes in ascending order.

Interview Quick-Check

Core Logic

The stack holds nodes whose left children have been fully explored but whose right children are yet to be visited, enabling the in-order traversal sequence.

State & Boundaries

The traversal continues while there are nodes in the stack or the current pointer is not null, ensuring all relevant nodes are visited.

2

Continue Iterative Inorder Traversal While Work Remains

6	`while stack or curr:`

Objective

To keep the iterative inorder traversal running while there is either a current node to descend into or deferred ancestor work stored on the stack.

Key Insight

Iterative inorder traversal has two sources of unfinished work: the current subtree path and the stack of deferred ancestors. The outer loop must continue while either exists; otherwise the traversal would terminate too early and miss nodes.

Interview Quick-Check

Core Logic

Continue while there is either a current node or a deferred ancestor on the stack.

State & Boundaries

The loop stops only when both the current pointer is null and the stack is empty.

Common Pitfalls & Bugs

If the outer loop ignores one of these two work sources, the inorder traversal becomes incomplete.

3

Traverse Left Subtree and Push Nodes onto Stack

7while curr:
8    stack.append(curr)
9    curr = curr.left

Objective

To reach the leftmost node by pushing all left children onto the stack, preparing for in-order visitation.

Key Insight

In-order traversal requires visiting the left subtree before the node itself. By pushing nodes onto the stack while moving left, the algorithm preserves the path to return to parent nodes after exhausting left descendants.

Interview Quick-Check

Core Logic

The inner loop pushes all left descendants onto the stack, ensuring the smallest nodes are processed first.

Common Pitfalls & Bugs

Failing to push nodes before moving left would lose track of parent nodes, breaking the traversal order.

4

Process Node, Decrement k, and Check for kth Element

11curr = stack.pop()
12k -= 1
13if k == 0:
14    return curr.val

Objective

To visit the current node, decrement the counter k, and return the node's value if it is the kth smallest.

Key Insight

Each node popped from the stack represents the next smallest element in the BST. Decrementing k tracks how many nodes have been visited. When k reaches zero, the current node is the kth smallest, allowing immediate termination.

Interview Quick-Check

Core Logic

Popping from the stack yields the next node in ascending order; decrementing k counts progress toward the kth smallest.

State & Boundaries

Returning immediately when k == 0 ensures the algorithm stops as soon as the kth smallest is found, optimizing runtime.

5

Move to Right Subtree to Continue Inorder Traversal

16	`curr = curr.right`

Objective

To shift traversal to the right child of the current node, continuing the in-order sequence.

Key Insight

After visiting a node, the algorithm must explore its right subtree to maintain in-order traversal order. Setting current to the right child prepares the next iteration to process this subtree.

Interview Quick-Check

Core Logic

Assigning current to the right child ensures the traversal proceeds correctly to nodes larger than the current one.

Common Pitfalls & Bugs

Neglecting to move to the right child would cause the traversal to miss nodes or enter an infinite loop.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 13 Critical

if k == 0:

Check if the current node is the kth smallest.

When k reaches zero, the current node is the desired element, enabling immediate return and early termination.

Line 8 Critical

stack.append(curr)

Push the current node onto the stack before moving left.

Pushing preserves the path back to parent nodes after exhausting left children, maintaining traversal order.

Line 11 Critical

curr = stack.pop()

Pop the top node from the stack to visit it.

Popping retrieves the next smallest node in the BST, following in-order sequence.

Line 14 Critical

return curr.val

Return the value of the kth smallest node.

Returning here stops traversal as the problem is solved, optimizing runtime by avoiding unnecessary work.

Line 3 Core

stack = []

Initialize an empty stack to simulate recursion for in-order traversal.

The stack stores nodes whose left children have been visited but whose right children are yet to be explored, enabling controlled traversal without recursion.

Line 12 Core

k -= 1

Decrement k to count the visited nodes.

Tracking k allows the algorithm to identify when the kth smallest node has been reached.

Line 6 Core

while stack or curr:

Continue traversal while there is either a current node or deferred work on the stack.

The outer loop keeps the iterative inorder traversal running until there are no deferred ancestors left on the stack and no current subtree left to descend into.

Line 7 Core

while curr:

Enter a loop to traverse down the left subtree.

This loop pushes all left descendants onto the stack, ensuring the smallest nodes are visited first in in-order traversal.

Line 9 Core

curr = curr.left

Move current pointer to the left child.

Descending left aligns with in-order traversal's requirement to visit left subtree before the node.

Line 16 Core

curr = curr.right

Move current pointer to the right child to continue traversal.

After visiting a node, the traversal must explore its right subtree to maintain the correct in-order sequence.

Line 4 Standard

curr = root

Set the current pointer to the root node to start traversal.

Starting at the root ensures the traversal covers the entire BST beginning from the smallest elements in the left subtree.

Test Your Understanding

Why does an in-order traversal of a BST produce nodes in ascending order, and how does this property enable early termination when searching for the kth smallest element?

In a BST, all left descendants are smaller than the node, and all right descendants are larger. In-order traversal visits left subtree, then node, then right subtree, naturally yielding sorted values. This ordering allows the algorithm to count nodes visited and stop immediately upon reaching the kth node, avoiding unnecessary traversal.

Don't just read it. Drill it.

Reconstruct Kth Smallest Element in a BST from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Kth Smallest Element in a BST drill

or drill a free problem

1	`class Solution:`
2	`def kthSmallest(self, root: TreeNode, k: int) -> int:`
3	`stack = []`
4	`curr = root`
5
6	`while stack or curr:`
7	`while curr:`
8	`stack.append(curr)`
9	`curr = curr.left`
10
11	`curr = stack.pop()`
12	`k -= 1`
13	`if k == 0:`
14	`return curr.val`
15
16	`curr = curr.right`

1	`class Solution {`
2	`public int kthSmallest(TreeNode root, int k) {`
3	`Deque<TreeNode> stack = new ArrayDeque<>();`
4	`TreeNode curr = root;`
5
6	`while (curr != null \|\| !stack.isEmpty()) {`
7	`while (curr != null) {`
8	`stack.push(curr);`
9	`curr = curr.left;`
10	`}`
11
12	`curr = stack.pop();`
13	`k--;`
14	`if (k == 0) {`
15	`return curr.val;`
16	`}`
17
18	`curr = curr.right;`
19	`}`
20
21	`throw new IllegalArgumentException();`
22	`}`
23	`}`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize Stack and Current Pointer for Traversal

Continue Iterative Inorder Traversal While Work Remains

Traverse Left Subtree and Push Nodes onto Stack

Process Node, Decrement k, and Check for kth Element

Move to Right Subtree to Continue Inorder Traversal

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.