Find the kth smallest node in a binary search tree

You're sitting in a Twitter interview, and the interviewer pulls up a binary search tree on the screen. "Given this tree and an integer k, can you find the kth smallest element?" This problem, also known as "Kth Smallest Element in a BST" on other platforms, is a staple at companies like Twitter and Facebook. It tests whether you understand the fundamental connection between BST structure and sorted order, and whether you can leverage that connection with a clean recursive solution.

TL;DR

Perform an in-order traversal of the BST to collect node values into a list. Because a BST's in-order traversal naturally produces values in ascending order, the kth smallest element is simply the value at index k - 1 in that list. This runs in O(n) time and O(n) space.

Why This Problem Matters

Finding the kth smallest element in a BST sits at the intersection of two core interview topics: tree traversal and sorted data access. It's a medium-difficulty problem that interviewers love because a strong candidate will immediately recognize the in-order traversal shortcut, while a less prepared candidate might try brute-force sorting. Once you internalize the relationship between BSTs and in-order traversal, a whole family of BST problems becomes straightforward.

Binary Search Trees: The Sorted Tree

A binary search tree is a binary tree with one critical property: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger.

This ordering constraint is what makes BSTs so useful for search operations. It also gives us a powerful shortcut for this problem.

Here's the BST we'll work with throughout this post:

The nodes in sorted order are: [2, 3, 4, 5, 7, 8, 10]. If k = 6, the answer is 8.

Understanding the Problem

Given: The root of a binary search tree and an integer k Find: The data value of the kth smallest node Constraint: The tree has at least k nodes and at most 1000 nodes

Here's the example from the problem:

kthSmallest(t1, 4) returns 8. The in-order sequence is [2, 4, 5, 8, 10], and the 4th element is 8.

Edge Cases to Consider

1. Single node: k must be 1, return that node's value
2. k equals 1: Return the leftmost (minimum) node
3. k equals n: Return the rightmost (maximum) node
4. Skewed tree: All nodes on one side, in-order still works correctly

The Key Insight: In-Order Traversal

If you've worked with BSTs before, you might already know the trick: an in-order traversal of a BST visits nodes in ascending order. Left subtree first, then the current node, then the right subtree. Since every left child is smaller and every right child is larger, this traversal pattern naturally produces a sorted sequence.

So the algorithm is straightforward:

1. Perform in-order traversal, collecting values into a list
2. Return the value at index k - 1

That's it. No sorting needed, no priority queues, no fancy data structures. The BST structure does the sorting for us.

Tracing Through the Traversal

Let's watch the in-order traversal build our sorted list step by step:

The traversal visits nodes in the order: 2, 3, 4, 5, 7, 8, 10. For k = 6, we grab dataValues[5] which is 8.

Implementation

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

import java.util.ArrayList;
import java.util.List;

public class Solution {
  public int kthSmallest(TreeNode root, int k) {
    // Build sorted list via in-order traversal
    List<Integer> dataValues = new ArrayList<>();
    buildInOrder(root, dataValues);

    // kth smallest is at index k-1
    return dataValues.get(k - 1);
  }

  private void buildInOrder(TreeNode node, List<Integer> dataValues) {
    if (node != null) {
      buildInOrder(node.left, dataValues);
      dataValues.add(node.data);
      buildInOrder(node.right, dataValues);
    }
  }
}

The solution has two parts. The kthSmallest method creates an empty list, fills it with the in-order traversal, and returns the element at position k - 1. The buildInOrder helper does the actual recursion: go left, add current value, go right. The null check is the base case that stops recursion at leaf boundaries.

Why k - 1?

Lists are zero-indexed but k is one-indexed. The 1st smallest is at index 0, the 2nd at index 1, and so on. So the kth smallest is always at dataValues.get(k - 1).

Complexity Analysis

Time Complexity: O(n)

We visit every node exactly once during the in-order traversal. Each visit does constant work: one null check, one recursive call left, one list append, one recursive call right. With n nodes total, the time is O(n).

Could we do better? Yes. If we stop the traversal after visiting k nodes, we'd achieve O(H + k) where H is the tree height. But the list-based approach is simpler to code and explain in interviews, and interviewers typically accept O(n) for this problem.

Space Complexity: O(n)

The ArrayList stores all n values, costing O(n) space. The recursive call stack adds O(H) space where H is the tree height. For a balanced BST, H = O(log n). For a skewed tree like this one, H = O(n):

Either way, the list dominates at O(n). If you want O(H) space, use the counter-based approach that stops after k visits without building the full list.

Common Pitfalls

1. Forgetting the BST property: Some candidates try to sort all node values. That works, but it's O(n log n) and completely misses the point. In-order traversal gives you sorted order for free.

2. Off-by-one on the index: k is 1-based, list indices are 0-based. Use k - 1, not k.

3. Modifying the tree: There's no need to change the tree structure. Just read values during traversal.

4. Using pre-order or post-order: Only in-order traversal produces sorted output on a BST. Pre-order gives root-first ordering, post-order gives leaves-first. Neither is sorted.

Interview Tips

When you see this problem:

1. Immediately mention in-order traversal: Saying "in-order traversal of a BST gives sorted order" signals strong fundamentals. This is the single most important thing to communicate.

2. Start with the list-based approach: It's clean, correct, and easy to explain. Don't over-optimize on the first pass.

3. Mention the optimization: After presenting the O(n) solution, mention that you could use a counter to stop after k visits. This shows you can think about efficiency without over-engineering.

4. Handle follow-ups gracefully: If asked "what if kth smallest is called many times?", talk about augmented BSTs where each node stores its subtree size. This is the order-statistic tree approach.

5. Draw the traversal: Sketch a small BST (3-5 nodes) and trace through the in-order traversal. Visually confirming the sorted output builds confidence in your solution.

Key Takeaways

• In-order traversal of a BST always produces values in ascending sorted order. This is the fundamental property that makes the problem simple.
• The kth smallest element is at index k - 1 in the in-order traversal list, since k is 1-indexed and arrays are 0-indexed.
• The list-based approach uses O(n) time and O(n) space. A counter-based early-termination approach can reduce this to O(H + k) time and O(H) space.
• This problem tests whether you understand BST structure deeply enough to avoid unnecessary sorting. Recognizing the in-order shortcut is what separates prepared candidates from unprepared ones.

Practice and Related Problems

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

• Find the minimum or maximum node in a BST (simpler, good warm-up)
• Validate whether a binary tree is a valid BST
• Find the lowest common ancestor in a BST
• Convert a BST to a sorted doubly linked list

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 tech companies. Whether you're targeting Twitter, Facebook, or your next dream role, building strong BST fundamentals will pay dividends across your entire interview prep.

Solutions in Other Languages

Python

class Solution:
    def kth_smallest(self, root, k):
        data_values = []
        self.build_in_order(root, data_values)
        return data_values[k - 1]

    def build_in_order(self, node, data_values):
        if node is not None:
            self.build_in_order(node.left, data_values)
            data_values.append(node.data)
            self.build_in_order(node.right, data_values)

JavaScript

class Solution {
  kthSmallest(root, k) {
    const dataValues = [];
    this.buildInOrder(root, dataValues);
    return dataValues[k - 1];
  }

  buildInOrder(node, dataValues) {
    if (node !== null) {
      this.buildInOrder(node.left, dataValues);
      dataValues.push(node.data);
      this.buildInOrder(node.right, dataValues);
    }
  }
}

TypeScript

class Solution {
  kthSmallest(root: TreeNode | null, k: number): number {
    const dataValues: number[] = [];
    this.buildInOrder(root, dataValues);
    return dataValues[k - 1];
  }

  buildInOrder(node: TreeNode | null, dataValues: number[]): void {
    if (node !== null) {
      this.buildInOrder(node.left, dataValues);
      dataValues.push(node.data);
      this.buildInOrder(node.right, dataValues);
    }
  }
}

C++

#include <vector>

class Solution {
public:
  int kthSmallest(TreeNode *root, int k) {
    std::vector<int> dataValues;
    buildInOrder(root, dataValues);
    return dataValues[k - 1];
  }

private:
  void buildInOrder(TreeNode *node, std::vector<int> &dataValues) {
    if (node != nullptr) {
      buildInOrder(node->left, dataValues);
      dataValues.push_back(node->data);
      buildInOrder(node->right, dataValues);
    }
  }
};

Go

func KthSmallest(root *TreeNode, k int) int {
    var dataValues []int
    buildInOrder(root, &dataValues)
    return dataValues[k-1]
}

func buildInOrder(node *TreeNode, dataValues *[]int) {
    if node != nil {
        buildInOrder(node.Left, dataValues)
        *dataValues = append(*dataValues, node.Data)
        buildInOrder(node.Right, dataValues)
    }
}

Scala

import scala.collection.mutable

class Solution {
  def kthSmallest(root: TreeNode, k: Int): Int = {
    val dataValues = mutable.ArrayBuffer[Int]()
    buildInOrder(root, dataValues)
    dataValues(k - 1)
  }

  private def buildInOrder(
    node: TreeNode,
    dataValues: mutable.ArrayBuffer[Int]
  ): Unit = {
    if (node != null) {
      buildInOrder(node.left, dataValues)
      dataValues.append(node.data)
      buildInOrder(node.right, dataValues)
    }
  }
}

Kotlin

class Solution {
    fun kthSmallest(root: TreeNode?, k: Int): Int {
        val dataValues = mutableListOf<Int>()
        buildInOrder(root, dataValues)
        return dataValues[k - 1]
    }

    private fun buildInOrder(node: TreeNode?, dataValues: MutableList<Int>) {
        if (node != null) {
            buildInOrder(node.left, dataValues)
            dataValues.add(node.data)
            buildInOrder(node.right, dataValues)
        }
    }
}

Swift

class Solution {
    func kthSmallest(_ root: TreeNode?, _ k: Int) -> Int {
        var dataValues = [Int]()
        buildInOrder(root, &dataValues)
        return dataValues[k - 1]
    }

    private func buildInOrder(_ node: TreeNode?, _ dataValues: inout [Int]) {
        if let node = node {
            buildInOrder(node.left, &dataValues)
            dataValues.append(node.data)
            buildInOrder(node.right, &dataValues)
        }
    }
}

Ruby

class Solution
  def kth_smallest(root, k)
    data_values = []
    build_in_order(root, data_values)
    data_values[k - 1]
  end

  def build_in_order(node, data_values)
    unless node.nil?
      build_in_order(node.left, data_values)
      data_values << node.data
      build_in_order(node.right, data_values)
    end
  end
end

Rust

impl Solution {
    pub fn kth_smallest(&self, root: Option<Box<TreeNode>>, k: i32) -> i32 {
        let mut data_values: Vec<i32> = Vec::new();
        Self::build_in_order(&root, &mut data_values);
        data_values[(k - 1) as usize]
    }

    fn build_in_order(node: &Option<Box<TreeNode>>, data_values: &mut Vec<i32>) {
        if let Some(current) = node {
            Self::build_in_order(&current.left, data_values);
            data_values.push(current.data);
            Self::build_in_order(&current.right, data_values);
        }
    }
}

Dart

class Solution {
  int kthSmallest(TreeNode? root, int k) {
    List<int> dataValues = [];
    buildInOrder(root, dataValues);
    return dataValues[k - 1];
  }

  void buildInOrder(TreeNode? node, List<int> dataValues) {
    if (node != null) {
      buildInOrder(node.left, dataValues);
      dataValues.add(node.data);
      buildInOrder(node.right, dataValues);
    }
  }
}

PHP

class Solution {
    public function kthSmallest(?TreeNode $root, int $k): int {
        $dataValues = [];
        $this->buildInOrder($root, $dataValues);
        return $dataValues[$k - 1];
    }

    private function buildInOrder(?TreeNode $node, array &$dataValues): void {
        if ($node !== null) {
            $this->buildInOrder($node->left, $dataValues);
            $dataValues[] = $node->data;
            $this->buildInOrder($node->right, $dataValues);
        }
    }
}

C#

public class Solution {
    public int kthSmallest(TreeNode? root, int k) {
        var dataValues = new List<int>();
        BuildInOrder(root, dataValues);
        return dataValues[k - 1];
    }

    private void BuildInOrder(TreeNode? node, List<int> dataValues) {
        if (node != null) {
            BuildInOrder(node.left, dataValues);
            dataValues.Add(node.data);
            BuildInOrder(node.right, dataValues);
        }
    }
}