Free Binary search trees lessonsBinary search trees · Stage 2 · Validate and repair · Step 1

Is it really a search tree

Check that every node of a binary tree respects the order rule against all of its ancestors, not just its parent, by passing allowed bounds down. About 14 minutes.

A range for every node

In a search tree, all values in a node's left subtree are smaller than the node, and all values in its right subtree are larger. That applies to every ancestor, not only the parent. So the value of a node must fit between bounds that come from the path above it.

The root has no bounds. Going to the left child sets an upper bound equal to the node's value. Going to the right child sets a lower bound equal to the node's value. Bounds from higher up are kept.

Go left: upper bound becomes the node's value.

Go right: lower bound becomes the node's value.

In code

def go(node, depth):
    if node is None:
        return
    go(node.left, depth + 1)
    go(node.right, depth + 1)

Is the tree 10, 5, 15, 3, 12, 11, 20 a search tree?

range: any

The root 10 has no bounds. Fine.

Move 1 of 3

Strictly between

At each node, check that the value is strictly above the lower bound and strictly below the upper bound, when those exist. A value equal to a bound breaks the rule, since all values are meant to be different.

An empty tree passes. Use a marker such as none for no bound, rather than a big number, since values can be as large as the integer range allows.

Strictly: equal to a bound is a failure.

No bound: use none, not a large number.

In code

too_small = lo is not None and v <= lo
too_big = hi is not None and v >= hi

Quick check

A node is larger than its parent but smaller than its grandparent, and it is in the grandparent's right subtree. Is that valid?

ANo, since everything in the right subtree must be larger than the grandparent
BYes, as it is larger than its parent
CIt depends on the other nodes

Show the answer

No, since everything in the right subtree must be larger than the grandparent. The rule applies to all ancestors, not only the parent.

Your problem

Validate binary search tree

Given the root of a binary tree, return true if it is a valid binary search tree: for every node, all values in its left subtree are strictly less than the node's value, all values in its right subtree are strictly greater, and both subtrees are valid. An empty tree is valid.

Example

root = [5, 4, 6, null, null, 3, 7] → false

0 ≤ number of nodes ≤ 10,000 · -2,147,483,648 ≤ node.val ≤ 2,147,483,647

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.