Kth Smallest Element in a BST

The problem

You are given the root of a binary search tree (BST) and a number rank. In a BST, every value in the left subtree of a node is smaller than the node, and every value in the right subtree is larger.

Return the rank-th smallest value in the tree. rank counts from 1, so rank = 1 asks for the smallest value.

Trees in the examples are written level by level, from left to right. null marks a missing child.

Example 1

Input: root = [7, 3, 10, 1, 5, null, 12, null, 2], rank = 3

Output: 3

Sorted, the values are 1, 2, 3, 5, 7, 10, 12. The 3rd one is 3.

Example 2

Input: root = [4, 2, 6], rank = 3

Output: 6

Sorted: 2, 4, 6. The 3rd one is the largest, 6.

Example 3

Input: root = [1], rank = 1

Output: 1

The only value is also the smallest.

Constraints

• The tree has n nodes. Call rank k, with 1 ≤ k ≤ n ≤ 10,000.
• 0 ≤ Node.val ≤ 10,000

Clarifying questions

Does rank count from 0 or from 1?

From 1. rank = 1 means the smallest value.

Is rank always valid?

Yes. 1 ≤ rank ≤ n, so the answer always exists.

Can values repeat?

No. In a BST here, left is strictly smaller and right strictly larger.

Is the tree balanced?

Not always. It can be a chain, so its height h can be as large as n.

Spot the pattern

The tree is a BST, and “k-th smallest” is about sorted order. An in-order traversal (left subtree, then the node, then the right subtree) of a BST visits the values in sorted order. So the k-th node it visits is the answer, and the walk can stop right there.

Solutions

Brute forceO(n)OptimalO(h + k)

Show all

This problem has two approaches. There is no useful step between them.

Brute force O(n)

The idea

Walk the whole tree in order and write every value into a list. Because the tree is a BST, the list comes out sorted. Then return the value at position k − 1, since lists count from 0.

It is short and correct. But it visits every node and stores every value, even when k is 1 and the answer is the very first value written.

Walkthrough

values

1. def inorder(node, values):
2. if node is None: return
3. inorder(node.left, values)
4. values.append(node.val)
5. inorder(node.right, values)
6. values = []
7. inorder(root, values)
8. return values[rank - 1]

In a BST, an in-order walk (left subtree, then the node, then the right subtree) visits the values from smallest to largest. Write them all down.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Brute force: write the whole tree out in order (left, node, right),
    // which gives the values sorted. Then pick position k. n steps, n memory.
    public int kthSmallest(TreeNode root, int rank) {
        List<Integer> values = new ArrayList<>();
        inorder(root, values);
        // rank counts from 1, the list from 0.
        return values.get(rank - 1);
    }

    private void inorder(TreeNode node, List<Integer> values) {
        if (node == null) return;
        // In a BST, everything smaller sits on the left, so it comes first.
        inorder(node.left, values);
        values.add(node.val);
        inorder(node.right, values);
    }
}

Big O

Time O(n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   There is no loop. The work repeats through recursion, so we count the calls of inorder. Each call does a fixed job: one check, two more calls and at most one append. So each call counts as 1 step.

   1. def inorder(node, values):
   2. if node is None: return
   3. inorder(node.left, values)
   4. values.append(node.val)
   5. inorder(node.right, values)
   6. values = []
   7. inorder(root, values)
   8. return values[rank - 1]

2. 2 Count the runs on Example 1

   Example 1 has 7 nodes, and each gets one call. Each of the 8 empty child spots also gets a call, which returns at once.

   7 + 8 = 15 calls.

   total calls

   7 nodes + 8 empty children = 15

3. 3 Write the count for any n

   A binary tree with n nodes has n + 1 empty child spots. Each node and each empty spot gets one call:

   n + (n + 1) = 2n + 1 calls

   Check it with Example 1: 2 × 7 + 1 = 15. The final lookup values[rank - 1] is 1 more step, which does not change anything.

4. 4 Keep only the part that grows fastest

   • Drop the + 1. One extra call does not change the growth.
   • Drop the 2. When n doubles, 2n doubles too.

   What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The list values holds all n values. The call stack also holds up to h calls, where h is the height, and h is at most n. The list is the bigger part, so the space is O(n).

   values (n items)call stack (h frames)

Very deep trees

Each recursive call waits until the calls below it finish. If the tree is one long line of 10,000 nodes, that is 10,000 calls waiting at once. The algorithm is still right, but every language limits how many calls can wait, so a very deep tree can crash with a "stack overflow". Here is how to raise the limit:

• Python: stops at 1,000 calls. The code above raises it with sys.setrecursionlimit.
• Java: run with java -Xss64m, or run the work in new Thread(null, task, "main", 64L << 20).
• C#: run the work in new Thread(task, 64 * 1024 * 1024).
• TypeScript (Node): run with node --stack-size=30000.
• Go: nothing to do. Its stack grows by itself.

Recursion is still the answer interviewers expect for trees. Mention the limit out loud: "for a very deep tree, I would raise the stack limit or keep my own stack in a loop."

Optimal O(h + k)

The idea

Do the same in-order walk, but by hand with a stack, a list where the last item in is the first out. Then the walk can stop the moment it reaches the k-th value.

The smallest value left is always at the far left. So walk left from the current node and push every node on the way. Pop the top: nothing smaller is still waiting, so it is the next value in order. Count it. If it is the k-th, return it. If not, the next values are in its right subtree, so go right and walk left again from there.

Why it never misses the answer: the stack produces exactly the in-order sequence, which is the sorted order. Counting pops counts sorted values, so the k-th pop is the k-th smallest.

Walkthrough

stack top →

empty

rank

3

1. stack, node = [], root
2. while True:
3. while node:
4. stack.append(node)
5. node = node.left
6. node = stack.pop()
7. rank -= 1
8. if rank == 0:
9. return node.val
10. node = node.right

The smallest value is at the far left. Walk there, and push each node on the way onto a stack, so we can come back up in order. Dim nodes are not reached yet, and stk marks nodes on the stack.

← BackStep →Play1 / 11

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // In-order walk with a stack, stopped at the k-th node. It only goes
    // down one path and then k nodes forward, so about h + k steps.
    public int kthSmallest(TreeNode root, int rank) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root;
        while (true) {
            // The smallest value left is at the far left. Remember the
            // path there, because each node on it comes next in order.
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            // This is the next value in sorted order.
            if (--rank == 0) return node.val;
            // Values just above this one live in its right subtree.
            node = node.right;
        }
    }
}

Big O

Time O(h + k)Space O(h)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The work is in the lit lines: each push walks one step left, and each pop takes one value. Both are a fixed job, so each push and each pop counts as 1 step. We count them.

   1. stack, node = [], root
   2. while True:
   3. while node:
   4. stack.append(node)
   5. node = node.left
   6. node = stack.pop()
   7. rank -= 1
   8. if rank == 0:
   9. return node.val
   10. node = node.right

2. 2 Count the runs on Example 1

   The table shows every step on Example 1. The walk pushes 7, 3 and 1 on its way down. Then it pops 1, pushes 2, pops 2, and pops 3, which is the 3rd pop.

   4 pushes + 3 pops = 7 steps.

   step	1	2	3	4	5	6	7
   action	push 7	push 3	push 1	pop 1	push 2	pop 2	pop 3
   k after	3	3	3	2	2	1	0

3. 3 Write the count for any n

   The walk stops at the k-th pop, so there are exactly k pops. A node is pushed only once, and every pushed node is either popped or still on the stack at the end. The stack holds at most one path, so at most h nodes. So:

   pops = k, pushes ≤ k + h, total ≤ 2k + h

   Check it with Example 1: k = 3 and h = 4, so the bound is 10. The real run used 7.

4. 4 Keep only the part that grows fastest

   Drop the 2. Doubling k does not change how the count grows with k. What is left is h + k. When k is small and the tree is balanced, that is far less than n. In the worst case, k = n and the walk visits every node, so it is never slower than the brute force.

   So the time is O(h + k).

5. S Space: count the extra memory the same way

   The stack holds the nodes on one path from the root down, so at most h of them. The code adds only node. So the space is O(h): about log n for a balanced tree, and n for a chain.

   stack (up to h nodes)node

Common mistake

Counting nodes when they are pushed

A node is pushed on the way down, before its smaller left values are seen. Count a node only when it is popped. That is the moment it takes its place in sorted order.

Tested at the limits

2,000 random search trees of 1 to 10 values, with every possible rank. The brute force and the optimal solution gave the same answer every time.

Largest inputs	Result
10,000 nodes in one long line to the left (the most allowed), with rank 10,000, so the walk passes every node. Optimal.	0.001 s, and about 0.08 MB of extra memory: the stack holds all 10,000 nodes at once, which is the O(h) space.
10,000 nodes, balanced, with rank 10,000. Optimal.	0.001 s, and under 0.01 MB of extra memory: the stack holds at most about 14 nodes.