Kth Smallest and Largest element in BST
MediumIn-order traversal, counting
Problem
Return the kth smallest (and/or kth largest) element in a BST.
An in-order walk of a BST visits values in sorted order — stop at the k-th one.
The idea
In-order visits a BST in ascending order, so the kth node visited is the kth smallest. Stopping as soon as the counter reaches k avoids traversing the rest, and reverse in-order gives the kth largest.
The trick
- Stop the traversal at k — do not build the whole list.
- Reverse in-order (right, node, left) for the kth largest.
- Storing subtree sizes makes repeated queries O(height).
Step 1 of 4. Inorder visits a BST in ascending order. Stop at the 3rd node.
1/4
Optimal
timeO(h + k)spaceO(h)
Count nodes inorder.
1let count = 0, answer = null;2function inorder(node) {3 if (!node || answer !== null) return;4 inorder(node.left);5 if (++count === k) { answer = node.val; return; }6 inorder(node.right);7}Input
- nodes
- 7, 6 edges
Memory
- count
- —
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- bst = [3,1,4,null,2], k = 1
- Output:
- 1
- Explanation:
- The smallest value is 1.
Example 2
- Input:
- bst = [5,3,6,2,4,null,null,1], k = 3
- Output:
- 3
- Explanation:
- The 3rd smallest is 3.
Example 3
- Input:
- bst = [2,1], k = 2
- Output:
- 2
- Explanation:
- Second smallest is 2.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.