Kth Smallest in a BST
MediumInorder visits keys in sorted order
Reading a search tree left-to-right gives sorted order, so the k-th one you visit is the answer.
The idea
An inorder traversal of a BST yields keys ascending. Walk inorder and stop at the kth visited node — no full sort required.
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.