Why it works
- In a binary search tree, in-order visits the values sorted, so prev is always the largest value smaller than the node.
- In a sorted list the closest pair is always two neighbours: anything further away is at least as far. So n − 1 comparisons with prev cover every pair that can win.
- The neighbour in sorted order is often not the parent: 24 is next to the root 20, two levels up.
Complexity
Time O(n): every node is visited once and compared once. Memory O(h), where h is the height of the tree: the call stack holds one path.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗