Kth Minimal Node in a Binary Search Tree

You're sitting in a Meta interview and the interviewer pulls up a binary search tree on the shared editor. "Given this BST and an integer k, return the kth smallest value." They pause. "And talk me through your approach before you code." This problem is a staple at Meta, Amazon, Apple, and Google because it directly tests whether you understand the relationship between BSTs and sorted data. Get the core insight right, and the code writes itself.

TL;DR

An in-order traversal of a BST visits nodes in ascending order. To find the kth smallest element, perform an iterative in-order traversal using a stack, counting each node as you pop it. When your counter hits k, return that node's value. This runs in O(H + k) time and O(H) space, where H is the tree's height. The iterative approach is preferred because you can stop the traversal immediately once you find the answer.

Why This Problem Matters

Finding the kth smallest element in a BST is a gateway problem for tree-based interviews. It tests two things at once: whether you understand the BST ordering property and whether you can translate that understanding into an efficient traversal. Companies ask it both as a standalone question and as a building block within larger problems like finding the median of a BST or validating BST structure.

BST Properties: The Foundation

Before jumping into the solution, let's revisit what makes a binary search tree special. In a BST, for every node, all values in the left subtree are smaller and all values in the right subtree are larger.

This ordering constraint is exactly what makes our solution possible. If you perform an in-order traversal (left, current, right), you visit nodes in sorted ascending order. For the tree above, the in-order sequence is: 1, 2, 3, 4, 5, 6.

The kth smallest element is simply the kth node visited during this traversal.

Understanding the Problem

Here's the problem setup:

Given: The root of a BST and a 1-based integer k Find: The kth smallest value in the tree Constraints: 1 ≤ k ≤ n ≤ 1000, where n is the number of nodes

Consider this example BST built from 3 1 4 # 2:

The in-order traversal visits: 1, 2, 3, 4. So kthSmallest(root, 1) returns 1, kthSmallest(root, 2) returns 2, and kthSmallest(root, 3) returns 3.

Edge Cases

1. Single node, k=1: The root itself is the answer
2. k equals n: You need to traverse the entire tree to reach the largest element
3. Skewed tree: All nodes on one side, so the stack grows to depth n

Solution Approach

The approach follows directly from the BST property. Since in-order traversal yields sorted order, we just need a way to walk through nodes one at a time and stop at position k.

We could do this recursively, but there's a practical advantage to the iterative approach: you maintain an explicit stack and can return immediately when you hit the kth node. With recursion, you'd need extra bookkeeping to propagate the result upward through the call stack.

Here's how the iterative in-order traversal works:

1. Start at the root. Push it and all its left descendants onto a stack.
2. Pop a node from the stack. This is the next smallest element.
3. Increment your counter. If it equals k, return this node's value.
4. Move to the popped node's right child and repeat from step 1.

The stack ensures you always process the leftmost (smallest) unvisited node next.

Walkthrough with the Example Tree

For the tree 3 1 4 # 2 with k = 1:

We push 3 and 1 onto the stack (going left), then pop 1. Count is 1, which equals k, so we return 1. Simple.

Walkthrough with a Larger Tree

For a more involved example, take the tree 5 3 6 2 4 # # 1 with k = 3:

The in-order sequence is 1, 2, 3, 4, 5, 6. We need the 3rd element.

Starting from the root, we push 5, 3, 2, and 1 onto the stack (the leftmost path). Then we pop 1 (count=1), pop 2 (count=2), and pop 3 (count=3). Since count equals k, we return 3 without visiting the remaining nodes.

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.*;

public class Solution {

  public int kthSmallest(TreeNode root, int k) {
    // Initialize a stack for the iterative in-order traversal
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    int count = 0;

    // Continue while there are nodes to process
    while (current != null || !stack.isEmpty()) {
      // Push all left descendants onto the stack
      while (current != null) {
        stack.push(current);
        current = current.left;
      }
      // Pop the next smallest node
      current = stack.pop();
      count++;
      // If this is the kth node, return its value
      if (count == k) {
        return current.data;
      }
      // Move to the right subtree
      current = current.right;
    }

    return -1; // Never reached with valid input
  }
}

The outer while loop keeps running as long as there are unvisited nodes (either current is non-null or the stack has entries). The inner while loop drives to the leftmost node of whatever subtree we're currently in. Each pop gives us the next element in sorted order.

Why the Inner Loop Works

Every time we enter the inner loop, we're saying: "Before I process this node, process everything smaller first." In a BST, everything smaller lives in the left subtree. So we push the current node (to process later) and move left. When we can't go left anymore, the top of the stack holds the smallest unprocessed node.

After processing a node, we move to its right child. If that child has its own left subtree, the inner loop will handle it on the next iteration. This guarantees sorted-order visitation without recursion.

Complexity Analysis

Time Complexity: O(H + k)

In the best case, the kth smallest element is near the leftmost path, and we pop k nodes after pushing H nodes. In the worst case (k = n or a skewed tree), we visit all n nodes, giving O(n).

Space Complexity: O(H)

The stack holds at most H nodes at any point, where H is the height of the tree. For a balanced BST, H = O(log n). For a completely left-skewed tree, H = O(n).

Alternative Approaches

Common Pitfalls

1. Forgetting the inner loop: Without pushing all left descendants first, you'll process nodes in the wrong order. The left-pushing loop is what converts a BST traversal into sorted visitation.

2. Off-by-one on the counter: The problem uses 1-based indexing. If you initialize count to 0 and check count == k after incrementing, you're correct. Starting at 1 or checking before incrementing will shift your answer.

3. Returning after the loop: If your code can reach the return statement after the while loop, something is wrong with the input constraints. For interview purposes, returning -1 is fine, but mention to the interviewer that valid input guarantees k <= n.

4. Using a recursive approach without early termination: A naive recursive in-order that collects all nodes into a list and returns the kth element wastes O(n) time and space even when k = 1.

Interview Tips

When presenting this solution in an interview:

1. Start with the BST insight: "In-order traversal of a BST visits nodes in ascending order. So the kth smallest is the kth node visited during in-order traversal."

2. Explain why iterative over recursive: "The iterative approach lets me stop immediately at the kth element without unwinding recursive calls."

3. Trace through a small example: Draw the tree 3 1 4 # 2, show the stack states for k=2, and demonstrate reaching the answer.

4. Mention follow-ups proactively: "If we needed to support frequent kth-smallest queries on a mutable BST, we could augment each node with a left-subtree count for O(H) queries."

5. Discuss edge cases: Single-node tree, k=1 (smallest element), k=n (largest element), and skewed trees.

Key Takeaways

• In-order traversal of a BST produces a sorted sequence. The kth smallest element is the kth node visited during this traversal.
• The iterative stack-based approach runs in O(H + k) time and O(H) space, and it stops as soon as the answer is found.
• Always push all left descendants before processing a node. This is the mechanism that guarantees sorted-order visitation.
• For interviews, the iterative approach is preferred because the counting and early termination logic is explicit and easy to trace on a whiteboard.
• If the BST is modified between queries, augment nodes with left-subtree counts for O(H) per query without full traversal.

Related Problems

Once you're comfortable with this problem, try these related BST challenges:

• Validate a binary search tree (uses the same in-order property)
• Find the lowest common ancestor in a BST
• Convert a BST to a sorted doubly linked list
• Find the kth largest element (reverse in-order traversal)

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top companies. Whether you're brushing up on tree traversals or grinding through your full interview prep, consistent practice on problems like this will build the pattern recognition that interviewers are looking for.

Solutions in Other Languages

Python

The Python solution uses a recursive helper with a mutable list to track count and result, avoiding the need for nonlocal declarations.

class Solution:
    def kth_smallest(self, root, k):
        count = [0]
        result = [None]

        def inorder_traversal(node):
            if node is None or result[0] is not None:
                return

            inorder_traversal(node.left)

            count[0] += 1
            if count[0] == k:
                result[0] = node.data
                return

            inorder_traversal(node.right)

        inorder_traversal(root)
        return result[0]

JavaScript

class Solution {
  kthSmallest(root, k) {
    let count = 0;
    let result = null;

    function inOrderTraversal(node) {
      if (!node || result !== null) return;

      inOrderTraversal(node.left);

      count++;
      if (count === k) {
        result = node.data;
        return;
      }

      inOrderTraversal(node.right);
    }

    inOrderTraversal(root);
    return result;
  }
}

TypeScript

class Solution {
    kthSmallest(root: TreeNode | null, k: number): number {
        let count = 0;
        let result: number | null = null;

        const inOrderTraversal = (node: TreeNode | null): void => {
            if (!node || result !== null) return;

            inOrderTraversal(node.left);

            count++;
            if (count === k) {
                result = node.data;
                return;
            }

            inOrderTraversal(node.right);
        };

        inOrderTraversal(root);
        return result!;
    }
}

C++

The C++ solution uses the iterative stack-based approach, matching the primary Java solution.

#include <stack>

class Solution {
public:
  int kthSmallest(TreeNode *root, int k) {
    std::stack<TreeNode*> stack;
    TreeNode* current = root;
    int count = 0;

    while (current != nullptr || !stack.empty()) {
      while (current != nullptr) {
        stack.push(current);
        current = current->left;
      }
      current = stack.top();
      stack.pop();
      count++;
      if (count == k) {
        return current->data;
      }
      current = current->right;
    }

    return -1;
  }
};

Go

func (s *Solution) KthSmallest(root *TreeNode, k int) int {
    var inorder func(node *TreeNode)
    var result int
    count := 0

    inorder = func(node *TreeNode) {
        if node == nil || count >= k {
            return
        }
        inorder(node.Left)
        count++
        if count == k {
            result = node.Data
            return
        }
        inorder(node.Right)
    }

    inorder(root)
    return result
}

Scala

class Solution {
  def kthSmallest(root: TreeNode, k: Int): Int = {
    var count = 0
    var result: Option[Int] = None

    def inOrderTraversal(node: TreeNode): Unit = {
      if (node == null || result.isDefined) return

      inOrderTraversal(node.left)

      count += 1
      if (count == k) {
        result = Some(node.data)
        return
      }

      inOrderTraversal(node.right)
    }

    inOrderTraversal(root)
    result.get
  }
}

Kotlin

import java.util.*

class Solution {
    fun kthSmallest(root: TreeNode, k: Int): Int {
        val stack = Stack<TreeNode>()
        var current: TreeNode? = root
        var count = 0

        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current)
                current = current.left
            }
            current = stack.pop()
            count++
            if (count == k) {
                return current.data
            }
            current = current.right
        }

        return -1
    }
}

Swift

class Solution {
    func kthSmallest(_ root: TreeNode?, _ k: Int) -> Int {
        var stack: [TreeNode] = []
        var current: TreeNode? = root
        var count = 0

        while current != nil || !stack.isEmpty {
            while current != nil {
                stack.append(current!)
                current = current!.left
            }
            current = stack.removeLast()
            count += 1
            if count == k {
                return current!.data
            }
            current = current!.right
        }

        return -1
    }
}

Ruby

class Solution
  def kth_smallest(root, k)
    stack = []
    current = root
    count = 0

    while !current.nil? || !stack.empty?
      while !current.nil?
        stack.push(current)
        current = current.left
      end
      current = stack.pop
      count += 1
      if count == k
        return current.data
      end
      current = current.right
    end

    -1
  end
end

Rust

Rust's ownership model makes the iterative approach more involved, since you need to move nodes in and out of the stack with take().

impl Solution {
    pub fn kth_smallest(&self, root: Option<Box<TreeNode>>, k: i32) -> i32 {
        let mut stack: Vec<Box<TreeNode>> = Vec::new();
        let mut current = root;
        let mut count = 0;

        while current.is_some() || !stack.is_empty() {
            while let Some(mut node) = current {
                current = node.left.take();
                stack.push(node);
            }
            let node = stack.pop().unwrap();
            count += 1;
            if count == k {
                return node.data;
            }
            current = node.right;
        }

        -1
    }
}

C#

using System.Collections.Generic;

public class Solution {
    public int KthSmallest(TreeNode? root, int k) {
        var stack = new Stack<TreeNode>();
        TreeNode? current = root;
        int count = 0;

        while (current != null || stack.Count > 0) {
            while (current != null) {
                stack.Push(current);
                current = current.left;
            }
            current = stack.Pop();
            count++;
            if (count == k) {
                return current.data;
            }
            current = current.right;
        }

        return -1;
    }
}

Dart

class Solution {
  int kthSmallest(TreeNode? root, int k) {
    List<TreeNode> stack = [];
    TreeNode? current = root;
    int count = 0;

    while (current != null || stack.isNotEmpty) {
      while (current != null) {
        stack.add(current);
        current = current.left;
      }
      current = stack.removeLast();
      count++;
      if (count == k) {
        return current.data;
      }
      current = current.right;
    }

    return -1;
  }
}

PHP

class Solution {
    public function kthSmallest(?TreeNode $root, int $k): int {
        $stack = new SplStack();
        $current = $root;
        $count = 0;

        while ($current !== null || !$stack->isEmpty()) {
            while ($current !== null) {
                $stack->push($current);
                $current = $current->left;
            }
            $current = $stack->pop();
            $count++;
            if ($count === $k) {
                return $current->data;
            }
            $current = $current->right;
        }

        return -1;
    }
}