Validate Binary Search Tree – Solution & Complexity

Watch: Validate Binary Search Tree with (low, high) bounds or an in-order check

Every value in a node's left subtree must be smaller and every value in its right subtree larger, all the way down, with no duplicates. Comparing each node with its parent isn't enough: in [5,4,6,null,null,3,7] the pairs 4 < 5, 6 > 5, 3 < 6 and 7 > 6 all pass, but 3 sits in 5's right subtree. Pass a range down instead: the root gets (−∞, +∞), a left child takes the node's value as its new high, a right child as its new low. Traced on that tree, 5 fits (−∞, +∞), 4 fits (−∞, 5), 6 fits (5, +∞), and 3 gets (5, 6) and fails, so the answer is false after 4 checks; 7 is never visited. The in-order traversal 4, 5, 3, 6, 7 drops at 3, the same answer. Compare strictly so [2,2,3] is invalid, and start at ±infinity, not INT_MIN/INT_MAX. O(n) time, O(h) space.

Solution Walkthrough

  1. Step 1: Recognize the Pattern

    The key pattern is: DFS carries the full valid value range. Identify the state and invariant before coding.

  2. Step 2: Build the Algorithm

    Advance one state transition at a time. Mark or update state before exploring dependent work.

  3. Step 3: Check Edge Cases

    Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.

  4. Step 4: Solution and Complexity

    Time: O(n). Space: O(h).

    Java/Go/Rust below are reference solutions for learning the pattern in those languages; only Python and JavaScript can be run and submitted for this problem, since the remote judge doesn't support the TreeNode structure yet.

    def is_valid_bst(root: TreeNode) -> bool:
        def valid(node, low, high):
            if node is None:
                return True
            return low < node.val < high and valid(node.left, low, node.val) and valid(node.right, node.val, high)
        return valid(root, float("-inf"), float("inf"))

FAQ