56.Validate Binary Search Tree

MediumBlind 75Trees · 11/15

Problem

Given the root of a binary tree, determine whether it is a valid binary search tree (BST). A valid BST satisfies, for every node:

every value in its left subtree is strictly less than the node's value,
every value in its right subtree is strictly greater than the node's value,
both subtrees are themselves valid BSTs.

Examples

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

Input:  root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root is 5, but its right child is 4, which is smaller than 5.

Input:  root = [5,4,6,null,null,3,7]
Output: false
Explanation: Every parent-child pair looks fine, but 3 sits in the right subtree of 5 while being smaller than 5.

Constraints

The number of nodes in the tree is in the range [1, 10^4].
-2^31 <= Node.val <= 2^31 - 1

💡 Key Insight

Comparing a node only with its direct children is not enough (example 3). Each node must respect all its ancestors, which collapses into a single open interval (low, high): going left tightens high to the parent's value, going right tightens low. Equivalently, an in-order traversal of a valid BST is strictly increasing.

Brute Force (Subtree Min/Max per Node)

TimeO(n²)SpaceO(h)

Intuition

For each node, the BST rule says the largest value in its left subtree must be smaller than it and the smallest value in its right subtree must be larger. Compute those extremes with helper traversals at every node.

Algorithm

If root is null, return true.
If root.left exists and max(root.left) >= root.val, return false.
If root.right exists and min(root.right) <= root.val, return false.
Return isValidBST(root.left) && isValidBST(root.right).

Visualization

root = [5,4,6,null,null,3,7]
        5
       / \
      4   6
         / \
        3   7

node 5: max(left) = 4 < 5 ok,  min(right) = 3 <= 5 -> false

Code

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (root.left != null && max(root.left) >= root.val) {
            return false;
        }
        if (root.right != null && min(root.right) <= root.val) {
            return false;
        }
        return isValidBST(root.left) && isValidBST(root.right);
    }

    // largest value anywhere in the subtree
    private int max(TreeNode node) {
        int best = node.val;
        if (node.left != null) best = Math.max(best, max(node.left));
        if (node.right != null) best = Math.max(best, max(node.right));
        return best;
    }

    // smallest value anywhere in the subtree
    private int min(TreeNode node) {
        int best = node.val;
        if (node.left != null) best = Math.min(best, min(node.left));
        if (node.right != null) best = Math.min(best, min(node.right));
        return best;
    }
}

Complexity

Time: O(n²) — every node scans its entire subtree; a skewed tree sums to O(n²).
Space: O(h) — recursion depth.

In-Order Traversal Must Be Increasing

TimeO(n)SpaceO(h)

Intuition

In-order traversal (left, node, right) of a BST lists values in sorted order. So the tree is valid iff each in-order value is strictly greater than the previous one. We do not need the list — just remember the previous value. An iterative stack makes it easy to stop early.

Algorithm

Use a stack and a pointer cur = root; keep prev = null.
While cur != null or the stack is not empty:
- Push cur and move left until cur is null.
- Pop a node; if prev != null and node.val <= prev, return false.
- Set prev = node.val, cur = node.right.
Return true.

Visualization

root = [5,1,4,null,null,3,6]
in-order: 1, 5, 3, 4, 6
              ^  3 <= 5 -> false

Code

java

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        Integer prev = null; // null = no value seen yet (handles Integer.MIN_VALUE)
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            if (prev != null && node.val <= prev) {
                return false; // in-order sequence not strictly increasing
            }
            prev = node.val;
            cur = node.right;
        }
        return true;
    }
}

Complexity

Time: O(n) — each node is pushed and popped once (less if we exit early).
Space: O(h) — the stack holds one root-to-leaf path.

DFS with Value BoundsOptimal

TimeO(n)SpaceO(h)

Intuition

Carry the allowed open interval (low, high) down the tree. The root may be anything. Moving to a left child, its values must also be below the parent, so high becomes parent.val; moving right, low becomes parent.val. A node outside its interval breaks the BST rule against some ancestor — exactly what example 3 needs. Using long bounds avoids trouble with values equal to Integer.MIN_VALUE / MAX_VALUE.

Algorithm

valid(node, low, high):
- If node is null, return true.
- If node.val <= low or node.val >= high, return false.
- Return valid(node.left, low, node.val) && valid(node.right, node.val, high).
Call valid(root, Long.MIN_VALUE, Long.MAX_VALUE).

Dry Run

flowchart TD
    N5["5<br/>range (-inf, +inf) ok"] --> N4["4<br/>range (-inf, 5) ok"]
    N5 --> N6["6<br/>range (5, +inf) ok"]
    N6 --> N3["3<br/>range (5, 6)<br/>3 <= 5 -> false"]
    N6 --> N7["7<br/>range (6, +inf)"]

Node 3 is a valid left child of 6, but it inherited the lower bound 5 from the root, so the check fails.

Code

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    // every value in this subtree must lie strictly inside (low, high)
    private boolean valid(TreeNode node, long low, long high) {
        if (node == null) {
            return true;
        }
        if (node.val <= low || node.val >= high) {
            return false;
        }
        return valid(node.left, low, node.val) && valid(node.right, node.val, high);
    }
}

Complexity

Time: O(n) — each node is checked once.
Space: O(h) — recursion depth.

Complexity Comparison

Approach	Time	Space
Brute Force (Subtree Min/Max per Node)	O(n²)	O(h)
In-Order Traversal Must Be Increasing	O(n)	O(h)
DFS with Value Bounds	O(n)	O(h)

Common Pitfalls

Checking only left.val < node.val < right.val for each parent-child pair — example 3 passes that test but is not a BST.
Using int sentinels like Integer.MIN_VALUE as bounds: a tree containing exactly Integer.MIN_VALUE would be wrongly rejected. Use long or nullable bounds.
Allowing duplicates: the rule is strict (< and >), so [2,2,2] is invalid.
In the in-order approach, initialising prev to Integer.MIN_VALUE has the same sentinel problem; start with null.