DSA Validating a BST

The problem

A binary search tree, or BST, follows one ordering rule. Every value in a node's left subtree is smaller than the node. Every value in its right subtree is bigger than the node. The rule must hold at every node, against every ancestor, not only against the parent.

Validation takes a tree and answers True or False. The code below builds three trees and prints each in level order beside its expected verdict. One of the three fools the obvious check, and that tree drives the whole article.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def level_order(root):
    if root is None:
        return []
    out = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node is None:
            out.append(None)
        else:
            out.append(node.value)
            queue.append(node.left)
            queue.append(node.right)
    while out and out[-1] is None:
        out.pop()
    return out

good = TreeNode(8, TreeNode(3, TreeNode(1), TreeNode(6)), TreeNode(10, None, TreeNode(14)))
subtle = TreeNode(10, TreeNode(5), TreeNode(15, TreeNode(6), TreeNode(20)))
plain = TreeNode(5, TreeNode(9), TreeNode(7))
print("good:", level_order(good), "expected True")
print("subtle:", level_order(subtle), "expected False")
print("plainly invalid:", level_order(plain), "expected False")
print("single node:", level_order(TreeNode(4)), "expected True")
print("empty tree:", level_order(None), "expected True")

The plainly invalid tree puts 9 on the left of 5, so any check spots it. The subtle tree is harder. Its node 6 sits under 15, which looks fine, but 6 also sits in the right subtree of 10, where every value must exceed 10.

Intuition

The first idea compares each node with its two children. Left child smaller, right child bigger, move on. Every parent-child pair in the subtle tree passes that test.

The trap is that a parent is not the only ancestor. Node 6 obeys its parent 15 and still breaks the rule set by its grandparent 10. A local check cannot see a bound set two levels up.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def level_order(root):
    if root is None:
        return []
    out = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node is None:
            out.append(None)
        else:
            out.append(node.value)
            queue.append(node.left)
            queue.append(node.right)
    while out and out[-1] is None:
        out.pop()
    return out

def naive(node):
    if node is None:
        return True
    if node.left is not None and node.left.value >= node.value:
        return False
    if node.right is not None and node.right.value <= node.value:
        return False
    return naive(node.left) and naive(node.right)

subtle = TreeNode(10, TreeNode(5), TreeNode(15, TreeNode(6), TreeNode(20)))
print("tree:", level_order(subtle))
print("parent-only check:", naive(subtle))
print("node 6 obeys its parent 15:", 6 < 15)
print("node 6 obeys its ancestor 10:", 6 > 10)

The parent-only check says True and the last line says False. Both facts are real. The verdict is wrong because the check never carried the ancestor bound down to node 6.

Brute force

A thorough route checks each node against its whole subtrees. For one node, scan every value in its left subtree and find the largest. Scan every value in its right subtree and find the smallest. The node passes only when the left largest is smaller and the right smallest is bigger.

The route is plainly correct. It is also wasteful, because each scan rewalks nodes that other scans already walked. The counter below bills every visit, scans included.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def level_order(root):
    if root is None:
        return []
    out = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node is None:
            out.append(None)
        else:
            out.append(node.value)
            queue.append(node.left)
            queue.append(node.right)
    while out and out[-1] is None:
        out.pop()
    return out

visits = 0

def subtree_values(node, out):
    global visits
    if node is None:
        return
    visits += 1
    out.append(node.value)
    subtree_values(node.left, out)
    subtree_values(node.right, out)

def brute(node):
    if node is None:
        return True
    left_vals = []
    subtree_values(node.left, left_vals)
    right_vals = []
    subtree_values(node.right, right_vals)
    if left_vals and max(left_vals) >= node.value:
        return False
    if right_vals and min(right_vals) <= node.value:
        return False
    return brute(node.left) and brute(node.right)

good = TreeNode(8, TreeNode(3, TreeNode(1), TreeNode(6)), TreeNode(10, None, TreeNode(14)))
subtle = TreeNode(10, TreeNode(5), TreeNode(15, TreeNode(6), TreeNode(20)))
visits = 0
print("good:", brute(good), "visits:", visits)
visits = 0
print("subtle:", brute(subtle), "visits:", visits)

Both verdicts are correct, including the subtle tree. The visit counts already exceed the node counts on seven-node trees. Each level of the tree makes the scans rewalk more of what sits below it.

The optimal solution: carry the bounds down

The key idea is one sentence. Each node inherits a low bound and a high bound from its ancestors, and it is valid exactly when its value sits strictly between them.

Going left keeps the low bound and makes the node's value the new high bound. Going right keeps the high bound and makes the node's value the new low bound. The root starts with no bound on either side.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def level_order(root):
    if root is None:
        return []
    out = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node is None:
            out.append(None)
        else:
            out.append(node.value)
            queue.append(node.left)
            queue.append(node.right)
    while out and out[-1] is None:
        out.pop()
    return out

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

good = TreeNode(8, TreeNode(3, TreeNode(1), TreeNode(6)), TreeNode(10, None, TreeNode(14)))
subtle = TreeNode(10, TreeNode(5), TreeNode(15, TreeNode(6), TreeNode(20)))
plain = TreeNode(5, TreeNode(9), TreeNode(7))
print("good:", valid(good, None, None))
print("subtle:", valid(subtle, None, None))
print("plainly invalid:", valid(plain, None, None))
print("single node:", valid(TreeNode(4), None, None))
print("empty tree:", valid(None, None, None))

Every case matches its expected verdict. Node 6 in the subtle tree arrives with a low bound of 10 from the root and a high bound of 15 from its parent. The value 6 is not above 10, so the check fails there, exactly where the fault lives.

Walkthrough

Follow the bounds down to node 6 in the subtle tree. The root is 10, its right child is 15, and the left child of 15 is 6. The trace prints the bounds each node receives.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def level_order(root):
    if root is None:
        return []
    out = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node is None:
            out.append(None)
        else:
            out.append(node.value)
            queue.append(node.left)
            queue.append(node.right)
    while out and out[-1] is None:
        out.pop()
    return out

def traced(node, low, high, depth=0):
    def show(x):
        return "-inf" if x is None else str(x)
    print("  " * depth + "node", node.value, "bounds: above", show(low), "and below", show(high))
    ok = (low is None or node.value > low) and (high is None or node.value < high)
    print("  " * depth + "inside bounds:", ok)
    if not ok:
        return False
    left = traced(node.left, low, node.value, depth + 1) if node.left else True
    right = traced(node.right, node.value, high, depth + 1) if node.right else True
    return left and right

subtle = TreeNode(10, None, TreeNode(15, TreeNode(6), None))
print("verdict:", traced(subtle, None, None))

The root 10 has no bounds. Node 15 inherits a low bound of 10 from the root, since it sits on the right. Node 6 then inherits that same low bound of 10 and gains a high bound of 15 from its parent. The value 6 fails its low bound, and the walk stops with False.

Complexity

Time is O(n) for the bounds check on a tree of n nodes. Each node is visited once and tested against two bounds.

Space is O(h) for a tree of height h. The bounds travel down the call stack, and no list or second pass is stored. The brute-force scans cost O(n squared) visits in the worst case, because each node's scans rewalk its subtrees.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def level_order(root):
    if root is None:
        return []
    out = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node is None:
            out.append(None)
        else:
            out.append(node.value)
            queue.append(node.left)
            queue.append(node.right)
    while out and out[-1] is None:
        out.pop()
    return out

visits = 0

def subtree_values(node, out):
    global visits
    if node is None:
        return
    visits += 1
    out.append(node.value)
    subtree_values(node.left, out)
    subtree_values(node.right, out)

def brute(node):
    if node is None:
        return True
    left_vals = []
    subtree_values(node.left, left_vals)
    right_vals = []
    subtree_values(node.right, right_vals)
    if left_vals and max(left_vals) >= node.value:
        return False
    if right_vals and min(right_vals) <= node.value:
        return False
    return brute(node.left) and brute(node.right)

def valid(node, low, high):
    global visits
    if node is None:
        return True
    visits += 1
    if low is not None and node.value <= low:
        return False
    if high is not None and node.value >= high:
        return False
    return valid(node.left, low, node.value) and valid(node.right, node.value, high)

def bst(sorted_vals):
    if not sorted_vals:
        return None
    mid = len(sorted_vals) // 2
    return TreeNode(sorted_vals[mid], bst(sorted_vals[:mid]), bst(sorted_vals[mid + 1:]))

for n in [7, 15, 31]:
    tree = bst(list(range(1, n + 1)))
    visits = 0
    brute(tree)
    b = visits
    visits = 0
    valid(tree, None, None)
    print("nodes:", n, "brute visits:", b, "bounds visits:", visits)

The bounds count equals the node count at every size. The scan count grows much faster, because each new level adds another full set of rewalks. The gap between the two columns is the whole reason for carrying bounds.

Edge cases and pitfalls

An empty tree is valid. It breaks no rule. A single node is valid for the same reason.

Equal values are the sharp edge. The BST rule here is strict, so a child equal to its parent fails on either side. A left child equal to the node breaks the high bound, and a right child equal to the node breaks the low bound.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def level_order(root):
    if root is None:
        return []
    out = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node is None:
            out.append(None)
        else:
            out.append(node.value)
            queue.append(node.left)
            queue.append(node.right)
    while out and out[-1] is None:
        out.pop()
    return out

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

print("empty:", valid(None, None, None))
print("single:", valid(TreeNode(4), None, None))
print("right child equal:", valid(TreeNode(5, None, TreeNode(5)), None, None))
print("left child equal:", valid(TreeNode(5, TreeNode(5)), None, None))
print("deep fault under 15:", valid(TreeNode(10, TreeNode(5), TreeNode(15, TreeNode(6), TreeNode(20))), None, None))
print("left chain descending:", valid(TreeNode(5, TreeNode(4, TreeNode(3))), None, None))

The duplicate verdicts deserve one more look. Both equal-child trees answer False. A looser BST definition allows duplicates on one side, but the strict bounds match the problem as stated here, and mixing the two definitions mid-check is a common source of wrong verdicts.