Validate Binary Search Tree

Problem

Given the root of a binary tree, determine whether it is a valid binary search tree. Recall the invariant from the concept lesson: at every node, all values in the left subtree must be strictly less than the node, and all values in the right subtree strictly greater.

Examples

      2                  5
     / \                / \
    1   3              1   4
                          / \
                         3   6

Constraints

1 ≤ n ≤ 10⁴ nodes · values fit in a 32-bit signed int (−2³¹ … 2³¹−1 — bites a naive bound later)

Attempt it first

This problem looks trivial and has a famous trap, so do not skip straight to code. Write down the check you'd perform at each node, then ask yourself: does it catch the second example above? Specifically — if you only compare each node to its immediate children, what happens at the node with value 5? Try to break your own solution before reading on.