Kth Smallest Element in a BST
MediumTrees
Given the root of a binary search tree and a number k, return the k-th smallest value in the tree, counting from 1: k = 1 asks for the smallest.
On this page the tree is written in level order, top to bottom and left to right, with null where a child is missing: [6, 3, 8, 1] is 6 with children 3 and 8, and 3 with a left child 1.
Examples
Input: root = [9, 4, 13, 2, 6, null, 15], k = 3 Output: 6
In order the values are 2, 4, 6, 9, 13, 15, and the third is 6.
Input: root = [50, 30, 70, 20, 40], k = 1 Output: 20
The smallest value is the leftmost node, 20.
Constraints
- The tree has n nodes,
1 ≤ k ≤ n ≤ 10⁴. 0 ≤ node.val ≤ 10⁴, and no two nodes share a value.
Stuck?
Hint 1
An in-order walk (left subtree, node, right subtree) visits a search tree’s values from smallest to largest.
Hint 2
Walk in order, with a stack or with recursion, and count the nodes as you visit them. The node that brings the count to k is the answer, and you can stop there.
The idea
An in-order walk visits a search tree's values from smallest to largest. Walk in order and count, and the k-th node visited is the answer, so the walk can stop there instead of visiting the whole tree.
Time O(h + k) for a tree of height hExtra space O(h)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
Walk in order without recursion. node is where the walk goes next and the stack holds the nodes waiting their turn; the walk is over only when both are empty.
function kthSmallest(root, k) { const stack = []; let node = root; while (node || stack.length) { while (node) { stack.push(node); node = node.left; } node = stack.pop(); k--; if (k === 0) return node.val; node = node.right; } return -1;}The trap
Collecting every value in order and then reading values[k] mixes two ways of counting. k counts from 1 and the array from 0, so it returns the next value up, and when k is the size of the tree it reads past the end and returns undefined. The in-order part is right, which makes the slip easy to miss.
function kthSmallest(root, k) { const values = []; const walk = (node) => { if (!node) return; walk(node.left); values.push(node.val); walk(node.right); }; walk(root); return values[k]; // k counts from 1, the array from 0}