medium

Kth Smallest Element in a BST

Use the fact that an in-order walk of a binary search tree is already sorted, and stop at the kth value.

1. Define the problem

Kth Smallest Element in a BST

You are given a binary search tree and a number k. Return the kth smallest value stored in it, counting from 1. The useful fact is that an in-order walk of a binary search tree visits the values in increasing order. So you do not need to sort anything: walk in order and stop at the kth value you see. The tree arrives as a level-order array such as [5, 3, 6, 2, 4, null, null, 1], with null for a missing child. Your function builds the tree and returns a single number.

Constraints

  • The number of nodes is between 1 and 104
  • 1 ≤ k ≤ number of nodes
  • 0 ≤ node value ≤ 104
  • Input is a level-order array with null for a missing child

Example

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

Explanation Walking the tree in order gives 1, 2, 3, 4, 5, 6. The third value in that list is 3, so the answer is 3.

2. Know the words first

In plain terms

Binary search tree
A binary tree kept in order: every value in a node’s left side is smaller than the node, and every value in its right side is larger.
In-order walk
Visit everything on the left, then the node itself, then everything on the right. On a binary search tree this produces the values from smallest to largest.
Counter
A number kept outside the walk that goes up by one each time a value is visited, so you know how far along the sorted order you are.
3. Visualize the solution

One cell per position in the sorted in-order sequence, filled as values are visited

One cell per position in the sorted in-order sequence, filled as values are visited
Statusinit

The tree is built; nothing has been visited yet.

What happens in this step

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

count = 0
answer = -1

The walk starts at the root 5 and dives left first,
down through 3 and 2 to the smallest value 1.
Step 1 of 5

Steps to visualize

  1. Each cell is the 1st, 2nd, 3rd and so on value of the in-order walk.
  2. Visiting in order means the cells fill from smallest to largest, left to right.
  3. A counter goes up on every visit; when it reaches k the walk can stop.
  4. Cells to the right of the answer stay empty because those nodes are never visited.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per position in the sorted in-order sequence, filled as values are visited
Statusinit

The tree is built; nothing has been visited yet.

What happens in this step

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

count = 0
answer = -1

The walk starts at the root 5 and dives left first,
down through 3 and 2 to the smallest value 1.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function kthSmallest(values, k) {
  function Node(value) {
    this.val = value;
    this.left = null;
    this.right = null;
  }

  function buildTree(list) {
    if (list.length === 0 || list[0] === null) {
      return null;
    }

    const root = new Node(list[0]);
    const queue = [root];
    let i = 1;

    while (i < list.length && queue.length > 0) {
      const node = queue.shift();

      if (list[i] !== null && list[i] !== undefined) {
        node.left = new Node(list[i]);
        queue.push(node.left);
      }

      i += 1;

      if (list[i] !== null && list[i] !== undefined) {
        node.right = new Node(list[i]);
        queue.push(node.right);
      }

      i += 1;
    }

    return root;
  }

  const root = buildTree(values);
  let count = 0;
  let answer = -1;

  function walk(node) {
    if (node === null || answer !== -1) {
      return;
    }

    walk(node.left);
    count += 1;

    if (count === k) {
      answer = node.val;
      return;
    }

    walk(node.right);
  }

  walk(root);

  return answer;
}
Time
O(h + k)
Space
O(h)
6. Test cases

Test cases

InputExpectedCovers
values = [5, 3, 6, 2, 4, null, null, 1], k = 33example from the docstring
values = [3, 1, 4, null, 2], k = 11k = 1 asks for the leftmost node
values = [1], k = 11a tree with only a root
values = [3, 1, 4, null, 2], k = 44k equals the number of nodes, so the answer is the largest value
values = [2, 1, 3], k = 22the answer is the root itself
values = [5, 3, 6, 2, 4, null, null, 1], k = 66the walk has to reach the far right of the tree

Keep reading