Kth Smallest Element in a BST
Kth Smallest Element in a BST is a medium Trees problem from the Blind 75. The key pattern is in-order traversal, and a good solution runs in O(h + k) time.
Problem
Return the kth smallest value in the supplied BST, where k starts at one.
Examples
Example 1
Input
{"tree":[6,3,8,2,5],"k":3}Output
5Example 2
Input
{"tree":[5,2,7,1,3],"k":2}Output
2Example 3
Input
{"tree":[9,4,12,2,6,null,null,1],"k":3}Output
4Approach
An in-order walk of a BST visits values in increasing order, so stop at the kth visited node.
| Pattern | In-order traversal |
|---|---|
| Time | O(h + k) |
| Space | O(h) |
Watch out for
k starts at one.