Problem 17.3 · Binary Search TreesMedium

Validate Binary Search Tree

What it teaches: Passing an allowed range down the tree.

Practise it on judges as “Validate Binary Search Tree”.

The problem

Return true if the tree is a valid BST: every left subtree holds only smaller values, every right subtree only larger values (strictly), at every node.

Example 1

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

Example 2

Input: root = [5, 1, 4, null, null, 3, 6]
Output: false

Constraints

1 ≤ nodes ≤ 10⁴
−2³¹ ≤ value ≤ 2³¹ − 1

Pattern clues in the wording

→ Check an ordering property across the whole tree

These clues point to BST Ordering: Use left < node < right to skip half the tree, and in-order traversal to visit values in sorted order.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public boolean isValidBST(TreeNode root) {
        return false;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	root = [2,1,3]	true
2	root = [5,1,4,null,null,3,6]	false
3	root = [5,4,6,null,null,3,7] 3 is in 5's right subtree	false

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Range recursion · O(n)2. In-order must increase · O(n)

Range recursion

Time O(n) Space O(h)

ok(n, lo, hi): null → true; n.val must be in (lo, hi); left gets (lo, n.val), right gets (n.val, hi).

Approach 1

class Solution {
    public boolean isValidBST(TreeNode root) {
        return ok(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

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

Verdict: The standard answer.

In-order must increase

Time O(n) Space O(h)

Walk in-order iteratively and check each value is larger than the previous one.

Approach 2

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

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

Verdict: Same cost; can stop at the first violation.

Before you submit

Edge cases and common mistakes

Test these inputs

Duplicates (invalid here)
Node equal to Integer.MAX_VALUE
Violation deep in the tree

Mistakes people make

Only comparing with the parent.
Using int bounds.

Interview

Follow-up questions

How would you recover a BST where exactly two nodes were swapped?