Validate Binary Search Tree

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

The in-order check and the range check visit each node once: O(n) time, with O(h) extra space for the range check's stack on a tree of depth h . Comparing every node with its whole subtrees 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 check only compares each value with the one before it, so keep the previous value in a variable instead of a list, and return false the moment a value is not larger. The extra space drops to O(h) for the recursion or stack.

Q: Can a binary search tree contain duplicate values?

Not under the strict definition used here: an equal value fits on neither side. Some textbooks allow equal values on one side, for example the right. Under that rule one strict comparison becomes ≤ .

MediumBinary search tree Tree traversal

+10

A binary tree is stored in the array tree in heap order: the root is at index 0, the children of index i are 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 isValidBST, which 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.

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: Read in order (left subtree, node, right subtree), the values are 1, 3, 6, 8, 10, 12, 15. They strictly increase, so every node sits on the correct side of every ancestor.

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 6 at index 5 is in the right subtree of the root, so it must be larger than 10.

Input: tree = [12, 7, 12]
Output: false
Explanation: The root's right child holds 12, equal to the root. The right subtree must be strictly larger, so the tree fails.

Follow-up

A node's parent is at index (i-1)/2, rounded down. Can you walk the tree in order with O(1) extra space, moving through parents instead of a stack or recursion?

Hints

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

0 of 3 opened

Solution

The rule covers whole subtrees, so comparing each node with its two children is not enough: a node deep down can break a limit set by an ancestor several levels up. Either read the tree in order and check that the values strictly increase, or pass each node the range its ancestors allow.

Compare each node with its whole subtrees

Intuition

Every value on a node's left is below its value v exactly when the largest value there is below v, and every value on its right is above v exactly when the smallest value there is above v. Two recursive helpers find them. An empty side returns -1 or 100001, outside the value range, so it never fails.

Each node is scanned once for every ancestor, about n × h visits for a tree of depth h. With a depth of at most 14 that is cheap, but on a 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 at 2*i+1 (-1 if empty) and the smallest in the right subtree at 2*i+2 (100001 if empty).
If the largest is at least tree[i], or the smallest is at most tree[i], return false.
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, so in a binary search tree it reads the values in sorted order.

The reverse holds too. For any node v, its whole left subtree comes right before it in the sequence 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 node alike.

The second example reads 5, 10, 6, 15, 20: the drop from 10 to 6 exposes the misplaced node. Each node is visited once: O(n) time, and O(n) space for the list.

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

Every ancestor puts one limit on a node: below a if the node is in the left subtree of an ancestor holding a, above a if it is in the right subtree. Together the limits form one open range (low, high), and the node is in the right place exactly when its value lies strictly inside it.

Build the range on the way down. A left child keeps low and gets high = v; a right child keeps high and gets low = v. In the second example, 15 passes (10, 15) to its left child, and the 6 fails at once. Values lie between 0 and 10^5, so -1 and 100001 serve as no limit. Each node is checked once, O(n) time, with O(h) nodes on the stack.

Algorithm

Push (0, -1, 100001): the root, with no real limit.
Pop (i, low, high). If tree[i] is not strictly between low and high, return false.
Push each real child: the left one at 2*i+1 with (low, tree[i]), the right one at 2*i+2 with (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

Comparing a node only with its children. In [10, 5, 15, -1, -1, 6, 20] every parent and child pair looks right, yet the 6 breaks the root's limit.
Allowing equal values. [12, 7, 12] is not valid: compare with <, never ≤.
Using 0 as the lower "no limit". It rejects the valid tree [0].
Reading a child without checking 2*i+1 < tree.length. In [12, 7, 12], index 3 is past the end.
In Lua and R, arrays start at 1. Keep node indexes 0-based for 2*i+1 and read tree[i + 1].

Frequently asked questions3

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

The in-order check and the range check visit each node once: O(n) time, with O(h) extra space for the range check's stack on a tree of depth h. Comparing every node with its whole subtrees 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 check only compares each value with the one before it, so keep the previous value in a variable instead of a list, and return false the moment a value is not larger. The extra space drops to O(h) for the recursion or stack.

Can a binary search tree contain duplicate values?

Not under the strict definition used here: an equal value fits on neither side. Some textbooks allow equal values on one side, for example the right. Under that rule one strict comparison becomes ≤.

def isValidBST(tree):
    # Write code here

Test #1

Test #2

Test #3

Argument

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

Expected Output

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 questions3

Similar problems