Difficulty: MediumTrees

Validate Binary Search Tree

Problem in Plain English

Given the root of a binary tree, determine whether it is a valid binary search tree, where every node in the left subtree is smaller and every node in the right subtree is larger than the node. The rule must hold for every descendant, not just the immediate children.

Problem Statement

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST requires that the left subtree of a node contains only nodes with values less than the node's value, and the right subtree contains only nodes with values greater than the node's value. Both the left and right subtrees must also be valid binary search trees, and duplicate values are not allowed.

Constraints

The number of nodes in the tree is in the range [1, 10^4].
-2^31 <= Node.val <= 2^31 - 1
Duplicate values are invalid. Initial bounds must allow both signed 32-bit extremes.

Examples

Example 1

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

The left subtree contains only 1, which is below 2; the right contains only 3, which is above 2. Both children are leaves.

Example 2

Input: root = [-2147483648]
Output: true

A singleton has no ordering conflicts. The minimum signed 32-bit value is legal and must not collide with an artificial initial bound.

Example 3

Input: root = [5,1,7,null,null,4,8]
Output: false

Every immediate child comparison passes, including 4 being left of 7. But 4 is also in the right subtree of 5, where all values must exceed 5.

Intuition

A node must satisfy every ancestor, not only its parent. In Example 1, 1 belongs below 2 and 3 belongs above it. You can either inspect every descendant for each ancestor, or carry the intersection of ancestor requirements as an open interval. Strict boundaries reject duplicates.

Approaches

Naive Subtree Check

Solution Details

Reveal Naive Subtree Check: intuition, complexity, and code

Intuition

For each node, directly check every value in its left subtree against that node and every value in its right subtree against it. This makes the full descendant requirement explicit, but a long chain repeats almost the same scan for each ancestor. Explicit stacks keep the snippet runnable on deep trees.

Step-by-Step Logic

Place root 2 on the pending-node stack and pop it.
Scan the left subtree: pop 1, confirm 1 < 2, and finish because it has no children.
Scan the right subtree: pop 3, confirm 3 > 2, and finish.
Push 3 then 1, so 1 is selected next; both of its subtree scans are empty.
Pop 3; both scans are empty. The pending stack is empty, so return true.

Why It Works

A subtree scan succeeds exactly when every visited descendant satisfies the strict comparison against the selected ancestor. The outer stack eventually selects every node, so every required ancestor-descendant relation is checked. A failed comparison proves an invalid relation; if all scans finish, all left and right subtree conditions hold. No node values or links are changed.

Dry Run

Naive Subtree Check: variable states at each step
event	pending stack (bottom to top)	scan stack	comparison / result
start	`[2]`	empty	no checks yet
pop ancestor 2, start left scan	`[]`	`[1]`	limit 2, below
pop 1	`[]`	`[]`	1 < 2 passes
start right scan	`[]`	`[3]`	limit 2, above
pop 3	`[]`	`[]`	3 > 2 passes
queue children	`[3,1]`	`[]`	both root scans passed
pop ancestor 1	`[3]`	`[]`	empty left and right scans pass
pop ancestor 3	`[]`	`[]`	empty left and right scans pass
finish	`[]`	`[]`	return true

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(h)

Let n be node count and h tree height. A valid chain performs (n-1)+(n-2)+...+1 descendant comparisons, giving quadratic worst-case time; a balanced tree takes O(n log n). The outer DFS stack and each temporary subtree DFS stack hold O(h) node references at once. Scans allocate fresh stacks repeatedly, but released stacks do not add to peak live space; the tree is read-only.

Code

Solution.java

1import java.util.ArrayDeque;2import java.util.Deque;3
4class TreeNode {5    int val;6    TreeNode left, right;7    TreeNode(int val) { this.val = val; }8}9
10class Solution {11    public boolean isValidBST(TreeNode root) {12        Deque<TreeNode> pending = new ArrayDeque<>();13        if (root != null) pending.push(root);14        while (!pending.isEmpty()) {15            TreeNode node = pending.pop();16            // Compare every descendant to this ancestor, not just its children.17            if (!scan(node.left, node.val, true) || !scan(node.right, node.val, false)) return false;18            if (node.right != null) pending.push(node.right);19            if (node.left != null) pending.push(node.left);20        }21        return true;22    }23    private boolean scan(TreeNode root, int limit, boolean below) {24        Deque<TreeNode> work = new ArrayDeque<>();25        if (root != null) work.push(root);26        while (!work.isEmpty()) {27            TreeNode node = work.pop();28            if (below ? node.val >= limit : node.val <= limit) return false;29            if (node.right != null) work.push(node.right);30            if (node.left != null) work.push(node.left);31        }32        return true;33    }34}

Hints

Hint 1

A parent-child comparison cannot detect 4 below the right child 7 of root 5.

Hint 2

The left subtree must stay below its parent while keeping every older lower bound; the right subtree keeps older upper bounds.

Hint 3

Use strict open bounds wider than signed 32-bit values, and an explicit stack to handle a 10000-node chain.

Edge Cases

A singleton at either signed 32-bit extreme is valid.
A duplicate anywhere in an ancestor subtree fails the strict inequality.
A descendant can satisfy its parent yet violate the root, as Example 3 does.
A 10000-node skewed tree must not depend on a language recursion limit; explicit stacks handle it safely.

Common Mistakes and Interview Tips

Checking only immediate children loses ancestor restrictions.
Using inclusive comparisons accepts duplicates.
Using Integer.MIN_VALUE and Integer.MAX_VALUE as exclusive Java bounds rejects valid endpoints; use long bounds.
Subtracting one from a bound or comparing by subtraction risks integer overflow.
Replacing only the current parent bound rather than inheriting the opposite bound forgets older ancestors.

Key Takeaway

When a rule involves every ancestor rather than only the parent, carry the accumulated constraint through the traversal instead of repeatedly scanning subtrees.