Validate Binary Search Tree — LC 98 Min Max Bounds DFS Interview Guide

Problem Statement#

Given the root of a binary tree, determine whether it is a valid Binary Search Tree (BST). A BST satisfies: every node in the left subtree is strictly less than the node, every node in the right subtree is strictly greater, and both subtrees are themselves valid BSTs.

Constraints:

• Number of nodes is in range 1 to 10000
• Node values fit in 32-bit signed integer range
• Strict inequality required (no duplicates allowed)

Input:  root = [2,1,3]
Output: true

Input:  root = [5,1,4,null,null,3,6]
Output: false
Explanation: 3 in the right subtree of 5 violates the BST property.

Why This Problem Matters#

LeetCode 98 Validate Binary Search Tree is one of the most frequently asked Medium tree problems across Amazon, Meta, Google, Apple, and Microsoft. It looks deceptively easy — most candidates write a wrong solution that only checks node.left.val < node.val < node.right.val for each node. That local check passes the example [5,1,4,null,null,3,6] while returning true on a tree that is clearly not a BST.

The interviewer is testing whether you understand the BST invariant globally: every node in the left subtree (not just the left child) must be less than the current node, and every node in the right subtree must be greater. This requires propagating bounds down the recursion, not just comparing parent and child.

The problem also surfaces edge cases involving integer limits — using INT_MIN and INT_MAX as bounds breaks when the tree contains those values. Strong candidates use -infinity / +infinity (Python float('-inf'), JavaScript -Infinity, Java Long.MIN_VALUE / Long.MAX_VALUE).

The Core Insight#

Every node in a BST has a valid range (low, high) determined by its ancestors:

• The root has range (-inf, +inf).
• When we recurse into the left child of a node with value v, the new range is (low, v) — the upper bound tightens to v.
• When we recurse into the right child, the new range is (v, high) — the lower bound tightens to v.

A tree is a valid BST if and only if every node's value lies strictly inside its propagated range. This single recursive function with two extra parameters captures the full BST invariant.

The alternate inorder approach works because inorder traversal of a BST yields a strictly increasing sequence. If any consecutive pair violates strict order, the tree is not a BST.

Visual Dry Run#

Tree: 5 -> {1, 4 -> {3, 6}}.

The local check 5 less than 4 would never trigger if we only compared parent to child — only 5's right subtree carrying the bound low = 5 catches it.

Solution (Optimal)#

class Solution:
    def isValidBST(self, root):
        def valid(node, low, high):
            if not node:
                return True
            if not (low < node.val < high):
                return False
            return (valid(node.left, low, node.val) and
                    valid(node.right, node.val, high))
 
        return valid(root, float('-inf'), float('inf'))

var isValidBST = function(root) {
    const valid = (node, low, high) => {
        if (!node) return true;
        if (node.val <= low || node.val >= high) return false;
        return valid(node.left, low, node.val) &&
               valid(node.right, node.val, high);
    };
 
    return valid(root, -Infinity, Infinity);
};

Time: O(n) — every node is checked once. Space: O(h) — recursion stack up to tree height; O(log n) balanced, O(n) skewed.

Common Mistakes#

• Only comparing each node to its immediate children, missing deeper-subtree violations
• Using INT_MIN and INT_MAX as bounds — fails when tree contains those values; use -inf and +inf or Long bounds
• Allowing equal values — the BST definition requires strict inequality
• Inorder approach forgetting the prev pointer or initializing it to a wrong value
• Returning early from the inorder approach without propagating false up the call chain

Interview Tips#

• Always sketch the failing example [5,1,4,null,null,3,6] to show the local-check trap
• Mention both approaches: bounds DFS (preferred) and inorder traversal (alternative)
• For the bounds approach, explicitly say "low and high tighten as we descend"
• Discuss that a valid BST has strict inequality, so duplicates make it invalid

Follow-up Questions#

• Allow duplicates (lazy BST) — change < to <= on one side consistently
• Validate BST with iterative inorder using a stack — same idea, no recursion
• Recover BST where exactly two nodes were swapped (LC 99) — inorder, find the misordered pair
• Largest BST subtree (LC 333) — return per-subtree bounds and size, like Tree DP

Key Takeaways#

• LeetCode 98 Validate BST is Medium and a top tree problem at Amazon, Meta, Google, Apple, and Microsoft
• Time is O(n); space is O(h) for recursion
• Pass propagated bounds (low, high) into recursion; tighten upper bound when going left, tighten lower bound when going right
• The local "parent vs child" check is wrong — must enforce the global range invariant
• Alternate solution: inorder traversal must produce a strictly increasing sequence
• Use -inf / +inf (or Long.MIN_VALUE / Long.MAX_VALUE) to avoid INT bound bugs
• Strict inequality required by definition; duplicates invalidate the BST