43. Kth Smallest Element in a BST

MediumTree BST DFS Stack

Given the root of a binary search tree and an integer k, return the k-th smallest value in the tree. k is 1-indexed: k = 1 asks for the minimum.

All values in the tree are distinct, and k is always between 1 and the number of nodes.

Example 1

Input: root = [5,3,7,2,4,6,8], k = 3
Output: 4

Explanation: In sorted order the values are 2, 3, 4, 5, 6, 7, 8; the third one is 4.

Example 2

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

Example 3

Input: root = [1], k = 1
Output: 1

Constraints

The number of nodes n is in the range [1, 10^4]
1 <= k <= n
-2^31 <= Node.val <= 2^31 - 1
All values are distinct

Follow-up: If the tree is modified often (inserts and deletes) and you are asked for the k-th smallest many times, how would you make each query faster than O(h + k)?

💡 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