Kth Smallest Element in a BST
You are given the root of a binary search tree and an integer k. In a binary search tree, every value in a node's left subtree is smaller than the node's value and every value in its right subtree is larger. All values are distinct.
Return the k-th smallest value stored in the tree, counting from 1 (so k = 1 asks for the minimum).
The tree is given in level order, with null marking a missing child: [5,3,8,null,4] is a root 5 with left child 3 and right child 8, where 3 has only a right child, 4.
Example 1
Example 2
Example 3
Constraints
The number of nodes isn, with 1 <= k <= n <= 1040 <= Node.val <= 106, all values distinct- The tree is a valid binary search tree
Pattern Path · Binary Search Trees · problem 101 of 169
Start simple
Collect every value with any traversal, sort the list and pick index k - 1: O(n log n) time and O(n) space.
The key idea
The ordering rule of a binary search tree means that an in-order traversal (left subtree, then the node, then the right subtree) visits values in increasing order. For any node, everything smaller is in its left subtree and is printed first, and everything larger comes after. So the k-th node an in-order walk visits holds the k-th smallest value.
Do the walk iteratively with a stack so you can stop as soon as the k-th node appears:
- Go as far left as possible from the current node, pushing each node on the way. The top of the stack is now the smallest value not yet visited.
- Pop it and count it. If this is the k-th pop, return its value.
- Otherwise move to its right child and repeat.
The walk touches the path down to the minimum and then k nodes, so the time is O(h + k), where h is the height. The stack holds at most one path, so the extra space is O(h). In a balanced tree h is about log n; in a fully skewed tree it can be n.
Complexity
- Time:
O(h + k) - Space:
O(h)
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
stack = []
node = root
while stack or node:
# Slide down to the smallest value not yet visited.
while node:
stack.append(node)
node = node.left
node = stack.pop()
k -= 1
if k == 0:
return node.val
node = node.rightJavaScript
/**
* Definition for a binary tree node (already provided):
* function TreeNode(val, left, right) {
* this.val = (val === undefined ? 0 : val);
* this.left = (left === undefined ? null : left);
* this.right = (right === undefined ? null : right);
* }
*/
var kthSmallest = function(root, k) {
const stack = [];
let node = root;
while (stack.length > 0 || node !== null) {
// Slide down to the smallest value not yet visited.
while (node !== null) {
stack.push(node);
node = node.left;
}
node = stack.pop();
k--;
if (k === 0) return node.val;
node = node.right;
}
};What the interviewer is checking
This tests whether you know that in-order traversal of a BST is sorted and can write an iterative traversal that stops early instead of building the whole list.
Mistakes to avoid
- Treating k as 0-based and returning the (k + 1)-th smallest.
- Traversing the whole tree and sorting, which ignores the BST property.
- Deep recursion on a skewed tree; the iterative stack avoids recursion limits.
Follow-ups to expect
- What if the tree is modified often and kth is asked often? (Store subtree sizes in each node.)
- How would you find the k-th largest? (Reverse in-order: right, node, left.)
- Can you do it in O(1) extra space? (Morris traversal.)
In real software
Order-statistic trees and database indexes answer "the k-th entry in sorted order" queries, for example paging through a sorted result set or finding a median, using the same in-order idea with subtree counts.