Why it works
- A call returns none exactly when its subtree holds neither p nor q, so at every node left and right say which sides hold them.
- If both sides found something, p and q are split between them, and no node lower down holds both: this node is the lowest. Every call above it hears back from one side only and just passes it up.
- If p were above q, the call on p would return p at once without looking below, and that is right: q is somewhere under p, so p is the answer.
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 ↗