Validate Binary Search Tree

The problem

You are given the root of a binary tree. Return true if it is a valid binary search tree (BST), and false if not. A tree is a valid BST when, at every node:

• every value in its left subtree is smaller than the node’s value,
• every value in its right subtree is larger than the node’s value,
• and both subtrees are valid BSTs too.

Trees in the examples are written level by level, from left to right. null marks a missing child.

Example 1

Input: root = [6, 3, 9, 1, 7]

Output: false

Each child looks fine next to its parent: 3 < 6 and 7 > 3. But 7 is in the left subtree of 6, and 7 is larger than 6.

Example 2

Input: root = [5, 2, 8, 1, 4, 7, 9]

Output: true

Everything left of 5 (2, 1, 4) is smaller, everything right (8, 7, 9) is larger, and the same holds under 2 and under 8.

Example 3

Input: root = [2, 2]

Output: false

The left child equals its parent. Values must be strictly smaller on the left, so equal is not allowed.

Constraints

• The tree has n nodes, where 1 ≤ n ≤ 10,000.
• -2³¹ ≤ Node.val ≤ 2³¹ − 1

Clarifying questions

Are equal values allowed?

No. Left must be strictly smaller and right strictly larger, so a repeated value makes the tree invalid.

Is it enough to compare each node with its children?

No. Example 1 passes every parent-child check and is still invalid. The rule covers whole subtrees.

Can a value be the smallest or largest 32-bit integer?

Yes. So the starting limits must sit outside that range, or be "no limit".

Can the tree be empty?

No. It has at least one node, and a single node is always valid.

Spot the pattern

The rule at one node depends on the values in its whole subtree. Turned around, each node must fit a range that its ancestors set: every time the path goes left, the parent becomes an upper limit, and every time it goes right, a lower limit. Passing that range down is a tree traversal where each call hands information down to its children.

Solutions

Brute forceO(n²)OptimalO(n)

Show all

This problem has two approaches. There is no useful step between them.

Brute force O(n²)

The idea

Check the rule exactly as it is written. At each node, find the largest value in its left subtree and the smallest value in its right subtree. The largest on the left must be smaller than the node, and the smallest on the right must be larger. Then check both children the same way.

The tree is not trusted yet, so finding the largest value means looking at every node of the subtree. Nodes deep in the tree get scanned again and again, once for each node above them.

Walkthrough

largest on the left so far

−∞

1. def is_valid(node):
2. if node is None:
3. return True
4. if node.left and largest(node.left) >= node.val:
5. return False
6. if node.right and smallest(node.right) <= node.val:
7. return False
8. return is_valid(node.left) and is_valid(node.right)

In a BST, every value in the left subtree of a node must be smaller than it, not just the left child. Start at the root, 6.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Brute force: at every node, scan its whole left subtree for the
    // largest value and its whole right subtree for the smallest. Up to n * n steps.
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        // Every value on the left must be smaller, not just the child.
        if (root.left != null && largest(root.left) >= root.val) return false;
        // Every value on the right must be larger.
        if (root.right != null && smallest(root.right) <= root.val) return false;
        return isValidBST(root.left) && isValidBST(root.right);
    }

    private long largest(TreeNode node) {
        // The tree is not trusted yet, so look at every node.
        if (node == null) return Long.MIN_VALUE;
        return Math.max(node.val, Math.max(largest(node.left), largest(node.right)));
    }

    private long smallest(TreeNode node) {
        if (node == null) return Long.MAX_VALUE;
        return Math.min(node.val, Math.min(smallest(node.left), smallest(node.right)));
    }
}

Big O

Time O(n²)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit lines call largest() and smallest(). Each one walks a whole subtree, one call per node, and each call is a fixed job: one compare and two more calls. So we count how many times a node gets scanned, and each scan is 1 step.

   1. def is_valid(node):
   2. if node is None:
   3. return True
   4. if node.left and largest(node.left) >= node.val:
   5. return False
   6. if node.right and smallest(node.right) <= node.val:
   7. return False
   8. return is_valid(node.left) and is_valid(node.right)

2. 2 Count the runs on Example 1

   When every check passes, a node is scanned once by each node above it: each ancestor looks through the subtree that holds it. So a node is scanned as many times as its depth. The picture shows it.

   0 + 1 + 1 + 2 + 2 = 6 scans. Example 1 stopped earlier, after 3 scans, because it failed at the root.

   scans if all checks pass

   0 + 1 + 1 + 2 + 2 = 6

3. 3 Write the count for any n

   The worst case is a valid tree shaped like a chain, where each node has one child. Then the nodes have depths 0, 1, 2 and so on up to n − 1:

   0 + 1 + 2 + … + (n − 1) = n × (n − 1) / 2 = ½n² − ½n

   Check it with a chain of 5 nodes: 5 × 4 / 2 = 10 = 0 + 1 + 2 + 3 + 4.

4. 4 Keep only the part that grows fastest

   • Drop the −½n. Next to ½n² it soon stops mattering.
   • Drop the ½. Halving every count does not change how fast it grows.

   What is left is n². A balanced tree does better, about n log n, but Big O names the worst case.

   So the time is O(n²).

5. S Space: count the extra memory the same way

   The code makes no list or map. The memory is the call stack: is_valid calls wait down one path, and largest() adds its own calls below them. In a chain both are about n deep, so the space is O(n).

   call stack (is_valid + largest)

Very deep trees

Each recursive call waits until the calls below it finish. If the tree is one long line of 10,000 nodes, that is 10,000 calls waiting at once. The algorithm is still right, but every language limits how many calls can wait, so a very deep tree can crash with a "stack overflow". Here is how to raise the limit:

• Python: stops at 1,000 calls. The code above raises it with sys.setrecursionlimit.
• Java: run with java -Xss64m, or run the work in new Thread(null, task, "main", 64L << 20).
• C#: run the work in new Thread(task, 64 * 1024 * 1024).
• TypeScript (Node): run with node --stack-size=30000.
• Go: nothing to do. Its stack grows by itself.

Recursion is still the answer interviewers expect for trees. Mention the limit out loud: "for a very deep tree, I would raise the stack limit or keep my own stack in a loop."

Optimal O(n)

The idea

Turn the rule around. Instead of asking each node about everything below it, let each node tell its children what they are allowed to be.

The root may hold any value: its range is (−∞, ∞). When we go left from a node, every value there must be smaller than that node, so the node becomes the new upper limit. When we go right, it becomes the new lower limit. The other limit is passed down unchanged. So a node’s range always holds the tightest limits from all its ancestors.

Now each node needs one check: is its value strictly inside its range?

Why it is correct: a value fits its range exactly when it is on the correct side of every ancestor. That is the BST rule, checked once per node instead of once per pair.

Walkthrough

1. def check(node, low=-inf, high=inf):
2. if node is None:
3. return True
4. if not (low < node.val < high):
5. return False
6. return check(node.left, low, node.val) and check(node.right, node.val, high)

Each node gets an open range (low, high) that it must fit in. Every ancestor tightens the range on the way down. Start with no limits. Under each node is its range: <6 means below 6, 3–6 means between 3 and 6.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Range limits: pass down the open range (low, high) each node must
    // fit in. One check per node, so n steps.
    public boolean isValidBST(TreeNode root) {
        // long limits sit outside the int range, so any value fits at first.
        return check(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean check(TreeNode node, long low, long high) {
        if (node == null) return true;
        // Every ancestor left a limit. low and high are the tightest ones.
        if (node.val <= low || node.val >= high) return false;
        // Going left, this node becomes the new upper limit.
        // Going right, it becomes the new lower limit.
        return check(node.left, low, node.val) && check(node.right, node.val, high);
    }
}

Big O

Time O(n)Space O(h)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   There is no loop. The work repeats through recursion, so we count the calls. Each call does a fixed job: one range check and at most two more calls. So each call counts as 1 step.

   1. def check(node, low=-inf, high=inf):
   2. if node is None:
   3. return True
   4. if not (low < node.val < high):
   5. return False
   6. return check(node.left, low, node.val) and check(node.right, node.val, high)

2. 2 Count the runs on Example 1

   The table lists the calls in order. 6, 3 and 1 fit their ranges. The two empty children of 1 return True at once. Then 7 fails its range (3, 6). The and stops the rest, so 9 is never called.

   6 calls.

   call	1	2	3	4	5	6
   node	6	3	1	empty	empty	7
   range	(−∞, ∞)	(−∞, 6)	(−∞, 3)			(3, 6)
   result	fits	fits	fits	True	True	False

3. 3 Write the count for any n

   In the worst case the tree is valid, so nothing stops early. Then each of the n nodes gets one call, and so does each of the n + 1 empty child spots:

   n + (n + 1) = 2n + 1 calls

   Check it with Example 2, which is valid: 7 nodes, so 2 × 7 + 1 = 15 calls.

4. 4 Keep only the part that grows fastest

   • Drop the + 1. One extra call does not change the growth.
   • Drop the 2. When n doubles, 2n doubles too.

   What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   Each call keeps two numbers, low and high. The calls that wait on the call stack form one path from the root down, so there are at most h of them, where h is the height of the tree. A balanced tree has h about log n, and a chain has h = n. So the space is O(h).

   lowhighcall stack (one frame per level)

Very deep trees

Each recursive call waits until the calls below it finish. If the tree is one long line of 10,000 nodes, that is 10,000 calls waiting at once. The algorithm is still right, but every language limits how many calls can wait, so a very deep tree can crash with a "stack overflow". Here is how to raise the limit:

• Python: stops at 1,000 calls. The code above raises it with sys.setrecursionlimit.
• Java: run with java -Xss64m, or run the work in new Thread(null, task, "main", 64L << 20).
• C#: run the work in new Thread(task, 64 * 1024 * 1024).
• TypeScript (Node): run with node --stack-size=30000.
• Go: nothing to do. Its stack grows by itself.

Recursion is still the answer interviewers expect for trees. Mention the limit out loud: "for a very deep tree, I would raise the stack limit or keep my own stack in a loop."

Common mistake

Checking only against the parent

Comparing each node with its own children passes Example 1, which is wrong. A node must also respect its grandparent and every ancestor above. The range carries all of them down at once.

Tested at the limits

2,000 random trees of 1 to 9 nodes: real search trees, search trees with one value changed, and random trees with repeated values. The smallest and largest allowed values show up too. The brute force and the optimal solution gave the same answer every time.

Largest inputs	Result
10,000 nodes in one long line (the most allowed), a valid search tree, so every node is checked. Optimal.	0.002 s, and about 1 MB of extra memory: 10,000 calls wait at once, one per level, which is the O(h) space.
10,000 nodes, balanced and valid. Optimal.	0.001 s, and under 0.01 MB of extra memory: only 14 calls wait at once.
2,000 nodes in one long line. Brute force.	0.35 s. It scans each subtree again for every node above it, so at 10,000 nodes it would make about 50 million calls.