LeetCode 230 · Trees

Kth Smallest Element in a BST, explained with a picture

Counting library shelves in order.

MediumTrees
▶ Watch it step by step

The problem

Given a binary search tree and k, return the k-th smallest value in it.

Input:  [5, 3, 6, 2, 4, null, null, 1], k = 3
Output: 3

Picture it

In a search tree, smaller values are always to the left. So reading the tree “left side, then the node, then right side” (an inorder walk) visits values in sorted order, like reading library shelves from left to right. We do that walk with a stack and stop at the k-th value.

How to recognise it

  • The tree is a binary search tree (BST): smaller values on the left, bigger on the right.
  • The question is about rank ("k-th smallest"), and an in-order traversal of a BST (left, node, right) visits values in sorted order.
  • So the answer is the k-th node of the in-order traversal, and you can stop as soon as you reach it.
  • Up to 10^4 nodes and 1 ≤ k ≤ n.

Start with brute force

Ignore the BST order: collect every value, sort, and pick position k − 1.

def kth_brute(root, k):
    vals = []
    def walk(node):
        if node:
            vals.append(node.val)
            walk(node.left)
            walk(node.right)
    walk(root)
    return sorted(vals)[k - 1]

It is O(n log n) time and O(n) space: about 1.3 × 10^5 steps for 10^4 nodes, which passes. But it sorts values the tree already keeps in order, and it reads the whole tree even when k = 1. A recursive in-order walk into a list is already sorted, which removes the sort but not the full walk.

From brute force to the idea

  1. Find the waste. The sort repeats work the BST already did, and the walk continues long after the k-th value has gone by.
  2. Walk in order. In-order traversal of a BST gives the values from smallest to largest, so count nodes as you visit them.
  3. Use your own stack. To be able to stop in the middle, the shown code keeps an explicit stack. while node: slides down left children, pushing each; the top of the stack is then the smallest unvisited value.
  4. Visit, count, move right. Pop a node, decrease k. If k reaches 0, this is the answer. Otherwise go to the node's right child, whose subtree holds the next values in order.

This is the key idea: an in-order walk of a BST is sorted, so stop after k visits.

The key idea

Inorder traversal of a BST is sorted; stop after k visits. O(height + k).

Python solution

def kth_smallest(root, k):
    stack, node = [], root
    while stack or node:
        while node:                    # slide down to the smallest
            stack.append(node)
            node = node.left
        node = stack.pop()
        k -= 1
        if k == 0:
            return node.val
        node = node.right

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute force (collect and sort)O(n log n): the sort dominatesO(n): every value in a list
Iterative in-order (shown code)O(h + k): slide down h levels, then visit k nodesO(h): the stack holds at most one root-to-node path

Here h is the height: about 14 for a balanced tree of 10^4 nodes, up to n for a chain.

Edge cases

  • k = 1: the leftmost node, found after the first slide down.
  • k = n: the largest value; the whole tree is visited.
  • Single node, k = 1: returns that value.
  • k larger than the number of nodes, or k = 0: the loop ends without a match and the function returns None (no exception). LeetCode guarantees 1 ≤ k ≤ n.
  • Very deep tree: a chain of 10^4 nodes works, because the stack is a Python list and no recursion is used.

Common mistakes

  • Checking k == 0 before decreasing it, which returns the (k + 1)-th value.
  • Forgetting node = node.right: the popped node is pushed straight back and popped again, so the function returns the smallest value for every k.
  • Using preorder or level order: those are not sorted, even in a BST.
  • Sorting the values, which works but throws away the BST property.
Your turn: k-th largest

Return the k-th largest value in a BST. For [5, 3, 6, 2, 4, null, null, 1] and k = 2 the answer is 5. Describe your approach, then write it if you like.

Compare with our answer

Run the in-order walk backwards: right, node, left. That visits values from largest to smallest, so the k-th visit is the answer. Swap every left and right in the shown code.

def kth_largest(root, k):
    stack, node = [], root
    while stack or node:
        while node:                    # slide down to the largest
            stack.append(node)
            node = node.right
        node = stack.pop()
        k -= 1
        if k == 0:
            return node.val
        node = node.left

Time O(h + k), space O(h). Using the k-th smallest with rank n − k + 1 also works but first needs the size n, which costs a full walk.

A strong answer mentions: reverse in-order order, stopping after k visits, and why counting the size first is wasteful.

Check what stuck

1. A BST holds 10^6 timestamps and you often need the 3rd earliest. Which approach fits best?

2. Why is the shown solution O(h + k) rather than O(n)?

3. In the shown code, what happens when k is larger than the number of nodes?

Score 60% or more and the lesson is marked complete.