Does the Tree Really Obey the Search Rule

Medium20–25 min

Topics

Binary Search TreeBSTValidationRecursion

Companies

AmazonMicrosoftFacebookGoogleBloomberg

You are given the root of a binary tree of integers. Decide whether it is a valid binary search tree: for every node, all values in its left subtree must be strictly smaller and all values in its right subtree strictly larger than the node's own value. Note that this concerns every descendant, not just the two children. Repeated values make the tree invalid. An empty tree is valid.

Listing the inorder values and checking that they strictly increase works. A single pass that hands each node the range of values it is allowed to have is more direct and stops at the first violation.

Test Case 1:

Input:root = [8, 4, 12, 2, 6, 10, 14]

Output:true

Explanation:Every node is larger than everything to its left and smaller than everything to its right.

Test Case 2:

Input:root = [10, 5, 15, null, null, 6, 20]

Output:false

Explanation:Each node looks fine next to its own children (15 has 6 and 20 below it), but 6 is in the RIGHT subtree of 10 and is smaller than 10.

Test Case 3:

Input:root = [5, 5]

Output:false

Explanation:The left child equals its parent; left values must be strictly smaller.

Constraints

◆0 ≤ number of nodes ≤ 100; −1000 ≤ node.val ≤ 1000; values may repeat
◆The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child
◆The tree is a valid binary search tree when, for EVERY node, all values in its left subtree are STRICTLY smaller and all values in its right subtree are STRICTLY larger (not just its two children — every descendant). A repeated value therefore makes the tree invalid
◆Return true if the tree is a valid binary search tree, false otherwise; an empty tree is valid

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — List the Values in Order and Check They Strictly Increase

Good

An inorder walk (left subtree, node, right subtree) of a valid search tree visits the values in strictly increasing order — and any violation of the rule, however deep, breaks that increase somewhere. So collect the inorder values in a list and check that every value is greater than the one before it (equal values count as a failure). O(n) time; the list needs O(n) extra space and the whole tree is always walked, even when an early failure is visible.

TimeO(n)

SpaceO(n)

Java

Try it out

class Solution {
    public boolean isValidBst(TreeNode root) {
        List<Integer> vals = new ArrayList<>();
        inorder(root, vals);
        for (int i = 1; i < vals.size(); i++) {
            if (vals.get(i) <= vals.get(i - 1)) return false;
        }
        return true;
    }

    private void inorder(TreeNode node, List<Integer> vals) {
        if (node == null) return;
        inorder(node.left, vals);
        vals.add(node.val);
        inorder(node.right, vals);
    }
}

Optimal — Pass Down the Allowed Range (Low, High) to Every Node

Optimal

Checking a node only against its parent is not enough: the rule is about ALL ancestors. Each node must lie strictly between a lower bound and an upper bound inherited from above. The root may be anything (bounds −∞ and +∞). Going to the left child, the upper bound becomes the current value; going to the right child, the lower bound becomes the current value. A node outside its range makes the tree invalid at once, and the && short-circuits so nothing else is examined. Use a wide type for the bounds (they start beyond the value range). O(n) time in the worst case, only recursion space (O(h)).