Find the k-th smallest and k-th largest element in a binary search tree (BST).
MediumUnlock detailed company stats for this questionUpgrade
Given the root of a binary search tree and an integer k, return the kth smallest value in the tree, counting from 1.
Trees in the examples and tests are written in level order, with null for a missing child.
Example 1
Input: root = [3, 1, 4, null, 2], k = 1 Output: 1 3 / \ 1 4 \ 2
Example 2
Input: root = [5, 3, 6, 2, 4, null, null, 1], k = 3 Output: 3
In sorted order, the values are 1, 2, 3, 4, 5, 6, and the third is 3.
Constraints
- The tree has
nnodes, where1 <= n <= 10^4. 1 <= k <= n0 <= Node.val <= 10^4
Approach
An in-order traversal visits a binary search tree's values in ascending order: the left subtree, then the node, then the right subtree. So the kth node an in-order traversal visits holds the answer. The iterative version keeps a stack of nodes whose left subtrees you're still exploring, which lets you stop the moment you reach the kth node instead of visiting the rest of the tree.
Steps
- Start at the root with an empty stack.
- Push nodes while moving left until there's no left child.
- Pop a node. It's the next value in sorted order, so subtract one from
k. Ifkis now0, return its value. - Move to the popped node's right child and repeat from step 2.
Complexity
- Time:
O(h + k), wherehis the height of the tree. You walk down to the smallest value, then visitknodes. - Space:
O(h), for the stack.
Common mistakes
- Collecting every value in a list before picking the
kth. It works, but it visits the whole tree and usesO(n)space. - Counting
kfrom zero. The smallest value isk = 1.
Interview experiences
1 sharedRelated questions
Find the K'th smallest element in an array.Find the floor and ceil values in a binary search tree (BST).Find the Largest Smaller BST KeyRelated courses

Course

Course
Course

