Validate Binary Search Tree

Q: Why is checking each node against its children not enough to validate a BST?

The rule covers whole subtrees. A node deep in the right subtree of the root must be larger than the root, even if it is the left child of a much larger node. In [10, 5, 15, -1, -1, 6, 20] , the 6 is a fine left child of 15 but sits on the right of 10 , so the tree is not a search tree. You need the limits from every ancestor, not only the parent.

Q: What is the time complexity of validating a binary search tree?

Both standard methods, the in-order check and the range check, look at each node once, so they take O(n) time. The range check needs O(h) extra space for the stack, where h is the depth. Comparing every node with its whole subtrees also works but costs O(n × h) , which reaches O(n²) on a tree shaped like a path.

Q: Can you validate a BST with an in-order traversal without storing every value?

Yes. The in-order check only ever compares a value with the one right before it, so keep the previous value in a variable instead of a list. Walk the tree in order with recursion or an explicit stack, and return false the moment a value is not larger than the previous one. That drops the extra space to O(h) .

Q: Can a binary search tree contain duplicate values?

Not under the strict definition used here: every left value must be smaller and every right value larger, so two equal values can never both fit. Some textbooks allow duplicates on one side, for example equal values to the right. Under that rule you would change one strict comparison into ≤ , so read the definition before you write the check.

MediumBinary search tree Tree traversal

+10

You get a binary tree stored in the array tree in level order. The root sits at index 0, the children of the node at index i sit at 2*i+1 (left) and 2*i+2 (right), -1 marks an empty spot, and the array may end with extra -1 entries.

Write a function named isValidBST that returns true if the tree is a binary search tree and false otherwise. In a binary search tree, every node's value is strictly greater than every value in its left subtree and strictly smaller than every value in its right subtree. Two equal values can never both be in a valid tree.

Function

isValidBST(tree: integer-array) → boolean

treeinteger-array: the binary tree in level order, with -1 for an empty spot
Returnsboolean: true if the tree is a binary search tree, false otherwise

Constraints

1 ≤ tree.length ≤ 32767
Each tree[i] is -1 or a value with 0 ≤ tree[i] ≤ 10⁵.
tree[0] is never -1, so the tree has at least one node.
The array may end with extra -1 entries past the last node.
Both children of an empty spot are empty too, and the depth is at most 14.
Values may repeat.

Examples

Input: tree = [8, 3, 12, 1, 6, 10, 15]
Output: true
Explanation: Each node sits on the correct side of every node above it. Read in order (left subtree, node, right subtree), the values come out as 1, 3, 6, 8, 10, 12, 15, strictly increasing, which is what a search tree gives.

Input: tree = [10, 5, 15, -1, -1, 6, 20]
Output: false
Explanation: Every node is larger than its left child and smaller than its right child, yet the tree is not valid. The 6 at index 5 sits in the right subtree of the root 10, so it must be larger than 10, and it is not.

Input: tree = [12, 7, 12]
Output: false
Explanation: The right child of the root holds 12, the same value as the root. The right subtree must be strictly larger, so an equal value breaks the rule.

+16 hidden tests on Submit

Follow-up

The parent of the node at index i sits at (i-1)/2, rounded down. Can you walk the tree in order with O(1) extra space, moving through parents instead of keeping a stack or recursing?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The rule is about whole subtrees, not about a node and its two children. A tree can pass the parent and child test at every node and still be wrong, because a node deep down can break a limit set by an ancestor several levels up. Two ideas handle that cleanly: read the tree in order and check that the values strictly increase, or hand every node the range of values its ancestors allow and check it against that range.

Compare each node with its whole subtrees

Intuition

First, how to move around the array. The node at index i has its left child at 2*i+1 and its right child at 2*i+2. A child is real only if its index is inside the array and the value there is not -1. In [10, 5, 15, -1, -1, 6, 20], the root 10 has 5 and 15 at indexes 1 and 2, and the 15 has 6 and 20 at indexes 5 and 6.

The first idea most people try compares each node with its two children only. That tree is the reason it fails: 5 < 10, 15 > 10, 6 < 15 and 20 > 15 all hold, but the 6 lives on the right of 10. The definition talks about every value in a subtree, so check exactly that.

For a node holding v, everything on its left is below v exactly when the largest value on its left is below v. In the same way, everything on its right is above v when the smallest value there is above v. Two small recursive helpers find that largest and that smallest value. For an empty side, the largest is -1 and the smallest is 100001, values outside the allowed range, so an empty side never fails.

This is correct, but it repeats work. A node is scanned once for every ancestor above it, so the total is about n × h visits for a tree of depth h. With a depth of at most 14 that is fine here, but on a tree that is one long path of n nodes it grows to O(n²).

Algorithm

Go through every index i whose value is not -1.
Find the largest value in the left subtree that starts at 2*i+1, or -1 if that spot is empty.
Find the smallest value in the right subtree that starts at 2*i+2, or 100001 if that spot is empty.
If the largest is at least tree[i], or the smallest is at most tree[i], return false.
After the last node, return true.

def isValidBST(tree):
    n = len(tree)

    def largest(i):
        # Largest value in the subtree at index i, or -1 when that spot is empty.
        if i >= n or tree[i] == -1:
            return -1
        return max(tree[i], largest(2 * i + 1), largest(2 * i + 2))

    def smallest(i):
        # Smallest value in the subtree at index i, or 100001 when that spot is empty.
        if i >= n or tree[i] == -1:
            return 100001
        return min(tree[i], smallest(2 * i + 1), smallest(2 * i + 2))

    for i in range(n):
        if tree[i] == -1:
            continue
        # Everything on the left must be smaller, everything on the right larger.
        if largest(2 * i + 1) >= tree[i] or smallest(2 * i + 2) <= tree[i]:
            return False
    return True

In-order values must strictly increase

Intuition

An in-order walk visits the left subtree, then the node, then the right subtree. In a binary search tree that order is sorted: everything on the left is smaller, so it comes first, and everything on the right is larger, so it comes after. The first example reads 1, 3, 6, 8, 10, 12, 15.

The reverse holds too, and that is what makes this a test. Take any node v. In the in-order sequence its whole left subtree sits right before it and its whole right subtree right after it. If the sequence strictly increases, every value before v is smaller and every value after it is larger, so the rule holds at v, and at every other node the same way.

So walk the tree in order, collect the values, and check each one against the one before it. The second example reads 5, 10, 6, 15, 20: the step from 10 down to 6 exposes the node on the wrong side. The third reads 7, 12, 12, and the repeated 12 fails the strict check. Each node is visited once, O(n) time, and the list takes O(n) space.

Algorithm

Write walk(i): if the spot is empty, stop; otherwise walk 2*i+1, append tree[i], then walk 2*i+2.
Call walk(0) to collect the values in order.
For each position k from 1, if values[k-1] ≥ values[k], return false.
Return true.

def isValidBST(tree):
    n = len(tree)
    values = []

    def walk(i):
        # Left subtree, then the node, then the right subtree.
        if i >= n or tree[i] == -1:
            return
        walk(2 * i + 1)
        values.append(tree[i])
        walk(2 * i + 2)

    walk(0)
    # A search tree read in order gives strictly increasing values.
    for k in range(1, len(values)):
        if values[k - 1] >= values[k]:
            return False
    return True

Carry the allowed range down the tree

Intuition

Look at the rule from a node's point of view. Every ancestor puts one limit on it. If the node sits in the left subtree of an ancestor holding a, its value must be below a; if it sits in the right subtree, above a. All those limits together form one open range (low, high), and the node is in the right place exactly when its value falls strictly inside that range.

You can build that range on the way down. The root has no limit. Stepping from a node holding v to its left child keeps low and lowers high to v; stepping to its right child keeps high and raises low to v. The new limit is always tighter than the one it replaces, because v itself passed the check against the old range.

In the second example, 15 gets the range (10, no limit) and passes it on to its left child as (10, 15). The 6 is below 10, so the check fails right there, without looking at any other node. Values are between 0 and 10^5, so -1 and 100001 serve as "no limit".

Keep the pending nodes on a stack, each with its range. Every node is checked once, O(n) time, and the stack holds the pending nodes along one path, O(h) space. The first broken range ends the search.

Algorithm

Push (0, -1, 100001): the root's index and an open range with no real limit.
Pop (i, low, high). If tree[i] is not strictly between low and high, return false.
If the left child 2*i+1 is real, push it with the range (low, tree[i]).
If the right child 2*i+2 is real, push it with the range (tree[i], high).
When the stack is empty, return true.

def isValidBST(tree):
    n = len(tree)
    # Each entry: a node index and the open range (low, high) its value must fall in.
    # -1 and 100001 lie outside every allowed value, so they mean "no limit".
    stack = [(0, -1, 100001)]
    while stack:
        i, low, high = stack.pop()
        value = tree[i]
        if not (low < value < high):
            return False
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and tree[left] != -1:
            stack.append((left, low, value))  # the left side must stay below value
        if right < n and tree[right] != -1:
            stack.append((right, value, high))  # the right side must stay above value
    return True

Pitfalls and edge cases

Most wrong answers check too little, or check the right thing with the wrong comparison.

Comparing a node only with its children. In [10, 5, 15, -1, -1, 6, 20] every parent and child pair looks right, and the 6 still breaks the limit set by the root two levels up.
Allowing equal values. The order is strict on both sides, so [12, 7, 12] is not valid. Use low < v < high and values[k-1] < values[k], never ≤.
Passing only the parent's value down. A left child needs both limits: below its parent and above whatever lower limit the parent had. Carry the full range.
Picking a "no limit" value that a node can hold. Values start at 0, so a lower limit of 0 would reject a valid node holding 0, as in [0]. Start below every allowed value.
Reading past the end of the array. Check 2*i+1 < tree.length before reading a child, and treat -1 as no child.
Mixing up the offset in Lua and R, where arrays start at 1. Keep the node indexes 0-based for the 2*i+1 arithmetic and read tree[i + 1].

Frequently asked questions4

Why is checking each node against its children not enough to validate a BST?

The rule covers whole subtrees. A node deep in the right subtree of the root must be larger than the root, even if it is the left child of a much larger node. In [10, 5, 15, -1, -1, 6, 20], the 6 is a fine left child of 15 but sits on the right of 10, so the tree is not a search tree. You need the limits from every ancestor, not only the parent.

What is the time complexity of validating a binary search tree?

Both standard methods, the in-order check and the range check, look at each node once, so they take O(n) time. The range check needs O(h) extra space for the stack, where h is the depth. Comparing every node with its whole subtrees also works but costs O(n × h), which reaches O(n²) on a tree shaped like a path.

Can you validate a BST with an in-order traversal without storing every value?

Yes. The in-order check only ever compares a value with the one right before it, so keep the previous value in a variable instead of a list. Walk the tree in order with recursion or an explicit stack, and return false the moment a value is not larger than the previous one. That drops the extra space to O(h).

Can a binary search tree contain duplicate values?

Not under the strict definition used here: every left value must be smaller and every right value larger, so two equal values can never both fit. Some textbooks allow duplicates on one side, for example equal values to the right. Under that rule you would change one strict comparison into ≤, so read the definition before you write the check.

Python

def isValidBST(tree):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

tree = [8, 3, 12, 1, 6, 10, 15]

Expected

true

Validate Binary Search Tree

Function

Constraints

Examples

Hints

Solution

Compare each node with its whole subtrees

In-order values must strictly increase

Carry the allowed range down the tree

Pitfalls and edge cases

Frequently asked questions4

Similar problems