Coding interview problems › Trees & BSTs

🌳 Trees & BSTs Medium

Kth Smallest Element in a BST

Kth smallest element in a BST explained: inorder traversal visits values in sorted order, so stop at the kth node. Tested Python code, pitfalls, live visual.

Also searched as: k-th smallest value in a binary search tree · inorder traversal stop at k

🌳

Try it live Free

Binary Search Tree & Traversals

Insert a handful of values in the BST lab and run in-order traversal: count along the output to see the k-th smallest appear at position k.

Open the playground →

The problem

Given the root of a binary search tree and an integer k (1-indexed), return the k-th smallest value stored in the tree.

Inputroot = [5, 3, 6, 2, 4, null, null, 1], k = 3
Output3

Sorted values are 1, 2, 3, 4, 5, 6.

The key insight

An inorder traversal of a BST visits values in sorted order. So the k-th node you visit in an inorder walk is the answer. An iterative walk with an explicit stack lets you stop the moment you reach k, instead of building the whole sorted list.

Brute force first: Collect every value, sort them, and index k - 1: O(n log n) and it ignores the BST property.

Step-by-step approach

  1. Use an explicit stack and a pointer node = root.
  2. Push nodes while moving left, so the smallest remaining value ends up on top.
  3. Pop a node: it is the next value in sorted order. Decrement k.
  4. If k reaches 0, return that node's value.
  5. Otherwise move to the popped node's right child and repeat.

Python solution

PYTHON 3tested
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right


def kth_smallest(root, k):
    stack, node = [], root
    while stack or node:
        while node:                    # walk to the smallest remaining value
            stack.append(node)
            node = node.left
        node = stack.pop()
        k -= 1
        if k == 0:
            return node.val
        node = node.right
    raise ValueError("k is larger than the number of nodes")

Complexity

TimeO(h + k)
SpaceO(h)

You walk down one left spine (h steps) and then pop k nodes, each pop costing amortised O(1). The stack never holds more than one root-to-leaf path.

Common mistakes

Frequently asked questions

What is the time and space complexity of finding the kth smallest in a BST?

O(h + k) time with an early-stopping inorder walk and O(h) space for the stack, where h is the height. In the worst case of a skewed tree that is O(n).

What if the tree is modified often and we query k-th smallest many times?

Store in every node the size of its subtree. Then you can decide at each node whether the answer is left, here or right, giving O(h) per query, and update sizes on insert and delete.

How do I find the kth largest instead?

Do a reverse inorder walk (right, node, left), which visits values in descending order, and stop at the k-th node.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Trees & BSTs Binary Search Tree & Traversals lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.