Start practising

Validate Binary Search Tree

Medium Trees & BST Postorder + Multiple Return Values Original on LeetCode

Validate Binary Search Tree is a medium trees & bst problem solved with the postorder + multiple return values pattern. The best approach, range check (dfs with bounds), runs in O(n) time and O(h) space. Below are 2 approaches in Java, from inorder must be strictly increasing up.

Problem

Decide whether a binary tree is a valid binary search tree: every node’s left subtree contains only smaller values, its right subtree only larger values, and both subtrees are BSTs themselves.

Examples

Example 1

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

Example 2

Input
root = [5, 1, 7, null, null, 4, 8]
Output
false
Why
4 is in 5's right subtree but smaller than 5, even though it is fine next to its parent 7.

Constraints

  • The tree has 1 to 10^4 nodes.
  • -2^31 <= Node.val <= 2^31 - 1; duplicates make it invalid.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Inorder must be strictly increasingO(n)O(h)
Range check (DFS with bounds)O(n)O(h)

1Inorder must be strictly increasing

TimeO(n)
SpaceO(h)

An inorder traversal of a valid BST is strictly increasing. Walk inorder and compare each value with the previous one.

  1. Iterative inorder; if cur.val <= prev, return false.
Java
class Solution {
    public boolean isValidBST(TreeNode root) {
        Deque<TreeNode> st = new ArrayDeque<>();
        TreeNode cur = root;
        Long prev = null;
        while (cur != null || !st.isEmpty()) {
            while (cur != null) { st.push(cur); cur = cur.left; }
            cur = st.pop();
            if (prev != null && cur.val <= prev) return false;
            prev = (long) cur.val;
            cur = cur.right;
        }
        return true;
    }
}

2Range check (DFS with bounds)

TimeO(n)
SpaceO(h)

Every node must lie strictly between the bounds its ancestors set. Going left, the upper bound becomes the node's value; going right, the lower bound does. Use long to handle extreme int values.

  1. valid(node, low, high): null → true.
  2. If val <= low or val >= high → false.
  3. valid(left, low, val) && valid(right, val, high).
Java
class Solution {
    public boolean isValidBST(TreeNode root) {
        return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean valid(TreeNode n, long low, long high) {
        if (n == null) return true;
        if (n.val <= low || n.val >= high) return false;
        return valid(n.left, low, n.val) && valid(n.right, n.val, high);
    }
}

Edge cases to test

  • Values equal to Integer.MIN_VALUE or MAX_VALUE (use long bounds)
  • A violation far below the ancestor
  • Equal values

Hints

Hint 1

Checking only the parent is not enough. Pass down the range (low, high) each node must fall in.

FAQ

What is the best time complexity for Validate Binary Search Tree?

Range check (DFS with bounds) runs in O(n) time and O(h) extra space.

Which pattern does Validate Binary Search Tree use?

It is a trees & bst problem that uses the postorder + multiple return values pattern. Other problems with the same pattern: Balanced Binary Tree, Children Sum in a Binary Tree, Largest BST.

Is there a brute force solution for Validate Binary Search Tree?

Yes. Inorder must be strictly increasing takes O(n) time and O(h) space. An inorder traversal of a valid BST is strictly increasing.

Which edge cases should I test for Validate Binary Search Tree?

Values equal to Integer.MINVALUE or MAXVALUE (use long bounds); A violation far below the ancestor; Equal values.