LeetCode Validate Binary Search Tree

LeetCode 98 — Validate Binary Search Tree — looks like a five-minute problem until you submit a five-minute solution and watch it fail. The trap is that “left is smaller, right is bigger” describes a local relationship, but a BST demands a global one. Every node has an implicit range it must live inside, and that range is the whole problem.

The Problem

Given the root of a binary tree, decide whether it is a valid binary search tree. A valid BST has:

• All nodes in the left subtree strictly less than the current node
• All nodes in the right subtree strictly greater than the current node
• Both subtrees themselves valid BSTs

The constraint that often gets missed: it must hold for every descendant, not just the immediate children.

Brute Force

The naive idea is to check each node against its two children. That misses cases like a left child that is smaller than its parent but greater than the parent’s parent. A slightly better brute force walks every node, collects its full left and right subtrees, and confirms the max of the left is less than the node and the min of the right is greater.

def isValidBST(root):
    def collect(node):
        if not node:
            return []
        return collect(node.left) + [node.val] + collect(node.right)

    def check(node):
        if not node:
            return True
        left = collect(node.left)
        right = collect(node.right)
        if left and max(left) >= node.val:
            return False
        if right and min(right) <= node.val:
            return False
        return check(node.left) and check(node.right)

    return check(root)

Correct, but every node re-walks its subtree, giving O(n^2) time.

Optimal Solution

The clean approach passes a (low, high) range down. The root starts with (-inf, +inf). When you recurse left, the upper bound becomes the current value; when you recurse right, the lower bound does. Any node outside its range fails immediately.

def isValidBST(root):
    def dfs(node, low, high):
        if not node:
            return True
        if node.val <= low or node.val >= high:
            return False
        return dfs(node.left, low, node.val) and dfs(node.right, node.val, high)

    return dfs(root, float("-inf"), float("inf"))

A second clean approach exploits the fact that an inorder traversal of a BST is strictly increasing. Walk inorder, track the previous value, and bail if anything is out of order.

Walk Through an Example

Consider the tree [5, 1, 4, null, null, 3, 6]. Visually:

• Root 5 with range (-inf, +inf) — passes.
• Left child 1 with range (-inf, 5) — passes.
• Right child 4 with range (5, +inf) — fails. 4 is not greater than 5.

The naive “check children only” version would have happily compared 4 to its parent 4 and to its children 3 and 6, and missed that 4 must also exceed 5.

Edge Cases

• A single-node tree is valid.
• An empty tree is valid by convention.
• Duplicate values are not allowed — the comparisons must be strict.
• Integer extremes matter. If a node holds 2**31 - 1, using regular ints as sentinels is fine in Python but breaks naive C++ ports. Use float("inf") or None as sentinels.
• A degenerate tree shaped like a linked list still works, but recursion may need an iterative variant for very deep trees.

Complexity Analysis

The optimal DFS visits each node once and does constant work, so time is O(n). Space is O(h) for the recursion stack, where h is tree height. A balanced tree gives O(log n), a skewed one O(n). The inorder iterative version has the same bounds. For why these matter, see Big-O Notation Explained.

How to Explain It in an Interview

Open with the trap: “Checking only immediate children is wrong because a node deep in the left subtree of the root must still be less than the root.” Then offer the fix: pass an allowed range down through DFS, tightening the upper bound on left moves and the lower bound on right moves. Mention the inorder traversal alternative as a sanity check — interviewers like seeing two angles. If asked about iterative versions, point at an explicit stack or Morris traversal.

Related Problems

• LeetCode 230 — Kth Smallest Element in a BST (also leans on inorder)
• LeetCode 235 — Lowest Common Ancestor of a BST
• LeetCode 99 — Recover Binary Search Tree
• LeetCode 108 — Convert Sorted Array to BST

All of them reward fluency with recursive thinking.

Wrap up

Validate BST is a vocabulary check: do you know what “valid” really means across the whole tree? Once you see that every node has an implicit range, the DFS writes itself. Memorize the min/max bounds pattern — it shows up in nearly every BST verification or construction problem you will face.