LeetCode 98 Validate Binary Search Tree - Example and Complexity Analysis

Trace the invalid tree 5(1, 4(3, 6)).

isValid(5, -∞, +∞): 5 in range. isValid(1, -∞, 5): 1 in range, leaf. ✓ isValid(4, 5, +∞): 4 NOT in (5, +∞). 4 < 5. ✗

Return false.

For valid tree 2(1, 3): isValid(2, -∞, +∞): 2 in range. isValid(1, -∞, 2): 1 in range. ✓ isValid(3, 2, +∞): 3 in range. ✓

Return true.

Visit each node once. $O(n)$ time. Recursion stack depth is tree height. $O(h)$ space.