Kth Smallest Element in a BST — Problem & Solution
Kth Smallest Element in a BST solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Kth Smallest Element in a BST is a medium coding problem on depth-first search and trees, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary search tree with distinct values and an integer k, return the k-th smallest value in the tree (counting from 1).
Example 1
Input: root = [3,1,4,null,2], k = 1
Output: 1
Explanation: In increasing order the values are 1, 2, 3, 4; the first is 1.
Example 2
Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
Explanation: In increasing order the values are 1, 2, 3, 4, 5, 6; the third is 3.
Example 3
Input: root = [2,1], k = 2
Output: 2
Explanation: The largest of two values is the second smallest.
Constraints
1 <= k <= number of nodes <= 10^40 <= Node.val <= 10^4all node values are distinctroot is a valid binary search tree
Follow-up: If the tree were modified often (inserts and deletes) and you had to answer this query many times, how would you speed it up?
Hints for Kth Smallest Element in a BST
Hint 1
An in-order traversal (left, node, right) of a binary search tree lists its values in increasing order.
Hint 2
You do not need the whole sorted list — only its k-th entry.
Hint 3
Run the in-order traversal iteratively with a stack and stop the moment the k-th node is popped.
How to solve Kth Smallest Element in a BST
In-order traversal visits a binary search tree's values in increasing order, so the k-th node it visits holds the answer; an explicit stack lets the walk stop right there.
Approach
- Start with an empty stack and
cur = root. - Push
curand move left untilcuris null. - Pop a node and decrease
k; ifkreaches 0, return the node's value. - Otherwise set
curto the popped node's right child and repeat.
Why it works
For every node, in-order visits all of its (smaller) left subtree, then the node, then its (larger) right subtree, so by induction the nodes are popped in increasing order of value. The k-th pop is therefore the k-th smallest value.
Complexity
- Time —
O(h + k), h the height of the tree - Space —
O(h)
Pitfalls
- k counts from 1.
- For the follow-up, store each node's subtree size: the rank of the root is then known and the search descends one side, O(h) per query.
Reference solution
Python
from typing import Optional
def kthSmallest(root: Optional[TreeNode], k: int) -> int:
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
k -= 1
if k == 0:
return node.val
node = node.right
return -1Java
public static int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode node = root;
while (!stack.isEmpty() || node != null) {
while (node != null) { stack.push(node); node = node.left; }
node = stack.pop();
if (--k == 0) return node.val;
node = node.right;
}
return -1;
}C++
int kthSmallest(TreeNode* root, int k) {
vector<TreeNode*> stack;
TreeNode* node = root;
while (!stack.empty() || node) {
while (node) { stack.push_back(node); node = node->left; }
node = stack.back();
stack.pop_back();
if (--k == 0) return node->val;
node = node->right;
}
return -1;
}JavaScript
var kthSmallest = function(root, k) {
var stack = [], node = root;
while (stack.length > 0 || node !== null) {
while (node !== null) { stack.push(node); node = node.left; }
node = stack.pop();
if (--k === 0) return node.val;
node = node.right;
}
return -1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals