How do you solve Kth Smallest Element in a BST?

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.

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 — DFS

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

Preview

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…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use an iterative in-order traversal with a stack. Push all left children onto the stack until none remain…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

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

Python

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

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

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.

3

Traverse Left Subtree and Push Nodes onto Stack

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

4

Process Node, Decrement k, and Check for kth Element

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

5

Move to Right Subtree to Continue Inorder Traversal

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

4 more steps with full analysis available on Pro.

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.

Full line-by-line criticality + rationale for all 11 lines available on Pro.

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?

See the answer with Pro.

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`