Why it works
- A tree is a BST exactly when its in-order values go strictly up, so it is enough to compare each value with prev, the one right before it.
- Comparing a node with its children is not enough: 6 < 15 is fine for a left child, yet 6 sits right of 10. In order, 6 comes straight after 10, and that is where it fails.
- The first false goes straight back up through every call, so the rest of the tree is never visited.
Complexity
Time O(n): each node is visited at most 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 ↗