Validate Binary Search Tree

The problem

Given root, the top node of a binary tree, return true if the tree is a binary search tree and false if it is not. Each node has a number val and two children, left and right; a missing child is null. A node's left subtree is its left child with everything below that child, and likewise on the right. In a binary search tree, for every node, all values in its left subtree are smaller than the node's value and all values in its right subtree are larger. Equal values are not allowed. An empty tree, where root is null, counts as a binary search tree.

What to write

type TreeNode = { val: number; left: TreeNode | null; right: TreeNode | null };

function solve(root: TreeNode | null): boolean

Input
root = {"val":2,"left":{"val":1,"left":null,"right":null},"right":{"val":3,"left":null,"right":null}}

Output
true

Input
root = {"val":2,"left":null,"right":{"val":2,"left":null,"right":null}}

Output
false

Constraints

0–500 acyclic tree nodes; finite integer values; duplicates invalid.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The tree has at most 500 nodes, so speed is not the hard part here. Getting the rule right is the hard part: the rule compares a node with every value in its two subtrees, not only with its two children, and never allows equal values.

2. Hint 2: Ask a smaller question

   A root holds 5 and its right child holds 7. You want to add a left child under the 7. It must be smaller than 7. Is every value smaller than 7 allowed, or does the 5 above have a say too?

3. Hint 3: Name the pattern

   What a node may hold depends on the nodes above it, so information has to travel down the tree. Give each node a range of allowed values: going left lowers the upper limit, going right raises the lower limit. Handing information from parent to child like this is preorder tree recursion. Read the lesson on preorder tree recursion.

4. Hint 4: State the invariant

   When you reach a node you hold two limits, the tightest ones that the nodes above it impose: a value it must be above and a value it must be below. The tree is a binary search tree exactly when every value lies strictly between its two limits.

5. Hint 5: Sketch the pseudocode

   check(node, low, high): if there is no node, return true. If the node's value is not strictly between low and high, return false. Otherwise return check(left child, low, value) and check(right child, value, high). Start with check(root, minus infinity, plus infinity).

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Pass strict lower and upper bounds down the tree. A left child narrows the upper bound and a right child narrows the lower bound, preserving ancestor constraints.

The slow way

The first idea is to compare each node with its two children. That is wrong: a node can agree with its parent and still break the rule of a node higher up. Comparing every node with all the values below it is correct, but a deep node is then visited once for each node above it.

The insight

Turn the rule around. A node does not have to look at everything below it. It only has to know what the nodes above it allow. Going left at one of them means staying below its value, and going right means staying above it. Two numbers hold all of that: a lower limit and an upper limit.

Step by step

1. Check each subtree against the limits set by the nodes above it. Every node above a subtree, on the way up to the root, restricts the values it may hold. Two numbers are enough to carry all those restrictions down: a lower limit and an upper limit.
2. An empty subtree breaks no rule. There is no value here that could be out of place. This case also ends the recursion below the last nodes and makes an empty tree valid.
3. The value must lie strictly between the two limits. The limits are values of nodes higher up that this node must be larger or smaller than. A value equal to a limit fails too, because the tree may not hold the same value twice.
4. Left subtree: same lower limit, this value as the upper limit. Everything on the left must be smaller than this node, so its value becomes the upper limit there. The lower limit is kept, because the rules from higher up still apply further down.
5. Right subtree: this value as the lower limit, same upper limit. Everything on the right must be larger than this node, so its value becomes the lower limit there, while the upper limit from higher up stays in force.
6. Start at the root, where no limit applies yet. No node sits above the root, so nothing restricts it. Minus infinity and plus infinity as limits let any value pass the first check.

The same numbered steps are the comments in each solution.

function solve(root) {
  // 1. Check each subtree against the limits set by the nodes above it
  function valid(node, low, high) {
    // 2. An empty subtree breaks no rule
    if (!node) return true;
    // 3. The value must lie strictly between the two limits
    if (node.val <= low || node.val >= high) return false;
    // 4. Left subtree: same lower limit, this value as the upper limit
    if (!valid(node.left, low, node.val)) return false;
    // 5. Right subtree: this value as the lower limit, same upper limit
    return valid(node.right, node.val, high);
  }
  // 6. Start at the root, where no limit applies yet
  return valid(root, -Infinity, Infinity);
}

type TreeNode = {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
};
function solve(root: TreeNode | null): boolean {
  // 1. Check each subtree against the limits set by the nodes above it
  function valid(node: TreeNode | null, low: number, high: number): boolean {
    // 2. An empty subtree breaks no rule
    if (!node) return true;
    // 3. The value must lie strictly between the two limits
    if (node.val <= low || node.val >= high) return false;
    // 4. Left subtree: same lower limit, this value as the upper limit
    if (!valid(node.left, low, node.val)) return false;
    // 5. Right subtree: this value as the lower limit, same upper limit
    return valid(node.right, node.val, high);
  }
  // 6. Start at the root, where no limit applies yet
  return valid(root, -Infinity, Infinity);
}

def solve(root):
    # 1. Check each subtree against the limits set by the nodes above it
    def valid(node, low, high):
        # 2. An empty subtree breaks no rule
        if node is None:
            return True
        # 3. The value must lie strictly between the two limits
        if not low < node.val < high:
            return False
        # 4. Left subtree: same lower limit, this value as the upper limit
        if not valid(node.left, low, node.val):
            return False
        # 5. Right subtree: this value as the lower limit, same upper limit
        return valid(node.right, node.val, high)

    # 6. Start at the root, where no limit applies yet
    return valid(root, float("-inf"), float("inf"))

Example 1, traced

Input
root = {"val":2,"left":{"val":1,"left":null,"right":null},"right":{"val":3,"left":null,"right":null}}

Output
true

Why it works

A limit that a node hands down is always tighter than the one it replaces, because the node itself passed its own check. So a value that lies between its two current limits obeys every node above it at once. Every node is checked this way, so every rule in the tree is checked.

Time and space

Time O(n), extra space O(h). Each node is visited once and compared with two numbers, so the time is O(n). The calls that are still waiting, one per level, are the only memory used: O(h) space, where h is the height, the number of levels in the tree.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Checking each node against its two children is not enough. Take root 5 with right child 7, where 7 has the left child 4. Every child agrees with its parent, but 4 is in the right subtree of 5.
• Keep both comparisons strict. If a value equal to its lower limit is accepted, the second example, a 2 with a 2 as its right child, wrongly returns true.
• Deal with a missing node before you read its value. The empty tree is one of the test cases, and reading a value where there is no node stops the program with an error.

Pattern

Preorder tree recursion. Builds on Lowest Common Ancestor of a Binary Search Tree and Count Good Nodes In Binary Tree.

Keep going