An auction house keeps bids in a binary search tree with distinct values. Return the second largest bid. Return None if there are fewer than two bids.
Examples
50
/ \
30 70
/ \ \
20 40 80
\
25
Input: root = build_tree([50, 30, 70, 20, 40, None, 80, None, 25])
Output: 70
10
\
20
/
15
Input: root = build_tree([10, None, 20, 15])
Output: 15
Input: root = build_tree([10, 5])
Output: 5
Constraints
0 <= number of nodes <= 3000- All values are distinct integers
- O(h) time, O(1) extra space
Goals
- Find the maximum and reason about where the next value can be
- Solve it in O(h) without a full traversal