Kth Smallest Element in a BST

MediumTree BST DFS Stack

An event store indexes event timestamps in a binary search tree. Timestamps are signed offsets from a reference epoch, so events before the epoch are negative, and no two events share a timestamp. A replay feature needs the k-th earliest event.

Given the root of the tree and an integer k, return the k-th smallest value in the tree, counting from 1: k = 1 asks for the earliest timestamp. k is always between 1 and the number of nodes.

Example 1

Input: root = [20,10,30,5,15,25,35], k = 4
Output: 20

Explanation: In time order the events are 5, 10, 15, 20, 25, 30, 35, and the fourth is 20.

Example 2

Input: root = [8,3,12,null,6], k = 3
Output: 8

Explanation: In time order the events are 3, 6, 8, 12.

Example 3

Input: root = [-5,-9], k = 2
Output: -5

Explanation: Both events happened before the epoch; the second earliest is -5.

Constraints

The tree has between 1 and 10^4 nodes.
k is between 1 and the number of nodes.
Values are distinct and fit in a 32-bit signed integer.

Follow-up: Events are inserted and deleted constantly while replays keep asking for different values of k. What extra information could each node store so that a query no longer has to walk past k nodes?

💡 Hint 1

Which traversal order visits the nodes of a BST in ascending order?

💡 Hint 2

An in-order traversal (left, node, right) produces sorted values. Count nodes as you visit them and stop at the k-th.

💡 Hint 3

With an explicit stack you can stop early instead of traversing the whole tree.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

An in-order traversal of a BST visits values in ascending order, so the answer is the k-th node it visits. Do the traversal iteratively: push nodes while walking left, pop one (the next smallest), decrement k and return its value when k reaches zero, otherwise continue into its right subtree. Only the nodes on the way to the answer are touched.

Time O(h + k)Space O(h), where h is the tree height

function kthSmallest(root, k) {
  const stack = [];
  let node = root;
  while (true) {
    while (node) {
      stack.push(node);
      node = node.left;
    }
    node = stack.pop();
    if (--k === 0) return node.val;
    node = node.right;
  }
}

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root;
        while (true) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            if (--k == 0) return node.val;
            node = node.right;
        }
    }
}

/**
 * Definition for a binary tree node (provided):
 * function TreeNode(val, left, right) { this.val = val ?? 0; this.left = left ?? null; this.right = right ?? null; }
 *
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
function kthSmallest(root, k) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit