Module 18 · Tree BFS, Binary Search Trees, and Tries

175. Validate a BST

Bridge · Download this solution · All solutions and shared helpers

Problem

Return whether a binary tree is a strict binary search tree: all values in a node's left subtree are smaller, and all values in its right subtree are larger. Duplicate values invalidate the tree. Values are integers; an empty tree is valid.

Examples

Example 1

valid_bst(build_tree([5,3,7,None,None,4,8]))
=> False

The value 4 violates an inherited lower bound of 5.

Example 2

valid_bst(build_tree([2,1,3]))
=> True

All strict subtree bounds hold.

Example 3

valid_bst(build_tree([2,2]))
=> False

Equal values are excluded.

Example 4

valid_bst(None)
=> True

There is no ordering violation.

Reveal the worked solution and reasoning

Why this mechanism works

A node must satisfy every ancestor's ordering restriction, not merely its parent's. Pass an open allowed interval down each call. Moving left replaces the upper bound with the current value; moving right replaces the lower bound. None represents an absent bound without assuming a fixed integer range.

State and boundaries

valid(node,low,high) requires every node in that subtree to lie strictly between the inherited bounds.

Protocol

Accept None.
Reject a value <=low or >=high when that bound exists.
Validate left with the current value as upper bound.
Validate right with it as lower bound.

Visualization

root 5 -> right child 7 -> left child 4
node 4 inherits interval (5,7)
4<7 locally, but 4<=5 violates the ancestor bound

Python implementation

from structures import build_tree

def valid_bst(root):
    def valid(node, low, high):
        if node is None:
            return True
        if low is not None and node.val <= low:
            return False
        if high is not None and node.val >= high:
            return False
        return (valid(node.left, low, node.val)
                and valid(node.right, node.val, high))
    return valid(root, None, None)

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

valid_bst(build_tree([5,3,7,None,None,4,8]))

L4 valid_bst: def valid(node, low, high):
root=N1(val=5,left=N2,right=N3)

L5 valid: if node is None:
node=N1(val=5,left=N2,right=N3); low=None; high=None

L5 valid: if node is None:
node=N2(val=3,left=None,right=None); low=None; high=5

L5 valid: if node is None:
node=None; low=None; high=3

L5 valid: if node is None:
node=None; low=3; high=5

L5 valid: if node is None:
node=N3(val=7,left=N4,right=N5); low=5; high=None

L5 valid: if node is None:
node=N4(val=4,left=None,right=None); low=5; high=7

Result: False. The value 4 violates an inherited lower bound of 5.

valid_bst(build_tree([2,1,3]))

L4 valid_bst: def valid(node, low, high):
root=N1(val=2,left=N2,right=N3)

L5 valid: if node is None:
node=N1(val=2,left=N2,right=N3); low=None; high=None

L5 valid: if node is None:
node=N2(val=1,left=None,right=None); low=None; high=2

L5 valid: if node is None:
node=None; low=None; high=1

L5 valid: if node is None:
node=None; low=1; high=2

L5 valid: if node is None:
node=N3(val=3,left=None,right=None); low=2; high=None

L5 valid: if node is None:
node=None; low=2; high=3

L5 valid: if node is None:
node=None; low=3; high=None

Result: True. All strict subtree bounds hold.

Why the solution is correct

Each inherited bound captures a necessary ancestor restriction. A successful current test plus recursively valid bounded child subtrees enforces all required comparisons, including distant ancestors. Conversely, a strict BST satisfies every propagated bound, so no valid tree is rejected.

Time and space

O(n) worst-case time and O(h) recursive stack space.

Common mistakes

Checking only immediate children accepts a right-subtree descendant smaller than the root. Non-strict comparisons would silently permit duplicates.

Reasoning card

State: valid(node,low,high) requires every node in that subtree to lie strictly between the inherited bounds.

Invariant: Every node in a call must lie strictly within its bounds.

Decision to rehearse: Local parent comparison is insufficient; carry global allowed range.

Finish: Validate right with it as lower bound

Transfer exercise

Validate by iterative inorder with a previous-value variable. Explain why a strictly increasing sequence is equivalent here.