Kth Smallest Element in a BST
The key idea
An in-order traversal of a BST visits node values in sorted ascending order. So the
k-th node visited in-order is exactly the k-th smallest value. You never need to sort or scan the whole tree: stop as soon as you have counted k nodes.Problem
You are given the root of a binary search tree and an integer k. Return the value of the k-th smallest element among all the node values, counting from 1 (so k = 1 asks for the smallest value in the tree). Recall that in a binary search tree every node's value is greater than all values in its left subtree and smaller than all values in its right subtree, which means an in-order walk of the tree produces the values in sorted order. The given k is always valid: 1 <= k <= n, where n is the number of nodes.
Constraints
- The number of nodes in the tree is
n. 1 <= k <= n <= 10^40 <= Node.val <= 10^4
Examples
Input: root = [3,1,4,null,2], k = 1
Output: 1
Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
Complexity
Time: O(H + k) Space: O(H)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree CamerasHARD
- Binary Tree Inorder TraversalEASY
- Binary Tree Maximum Path SumHARD
- Binary Tree PathsEASY
- Binary Tree Postorder TraversalEASY
- Binary Tree Preorder TraversalEASY
- House Robber IIIMEDIUM
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Construct Binary Tree from Preorder and Inorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Complete Tree NodesEASY