Card 03/ 09
Checking Only Each Node's Children
A tree can pass the check at every parent and still break the order deeper down.
Checking that a binary tree is a valid binary search tree means checking every key against the range its position allows, not only against its parent. This card covers why comparing each node with its two children is not enough, and the check that carries a lower and an upper bound down the tree instead.
The natural first attempt visits every node and confirms that its left child is smaller and its right child larger. It feels complete, because every parent and child pair is checked. The tree below passes it: 3 is smaller than 5, and 6 is larger than 3. But 6 sits in the left subtree of 5, where every key must be smaller than 5, so the tree is not a binary search tree. A search for 6 would go right from 5, find nothing there, and report a key that is in the tree as missing.
5, allows any key
3, allows keys below 5
null, empty left link
6, allows keys between 3 and 5: breaks the order
null, empty right link
The listing runs both checks on that tree and on a valid one, which has 4 where the first has 6. children_only compares each node with its children, highlighted near the top. within_bounds passes each node the open interval its key must lie in: the root accepts anything, and going left makes the current key the new upper bound, while going right makes it the new lower bound. Its printed lines show each key against its bounds.
import math
class Node:
def __init__(self, key, left=None, right=None):
self.key = key
self.left = left
self.right = right
def children_only(node):
if node is None:
return True
if node.left is not None and node.left.key >= node.key:
return False
if node.right is not None and node.right.key <= node.key:
return False
return children_only(node.left) and children_only(node.right)
def within_bounds(node, low=-math.inf, high=math.inf):
if node is None:
return True
if not low < node.key < high:
print(f" {node.key} is outside ({low}, {high})")
return False
print(f" {node.key} is inside ({low}, {high})")
return within_bounds(node.left, low, node.key) and within_bounds(node.right, node.key, high)
def in_order(node, keys):
if node is not None:
in_order(node.left, keys)
keys.append(node.key)
in_order(node.right, keys)
return keys
trees = {
"5, left 3, 3's right 6": Node(5, Node(3, None, Node(6))),
"5, left 3, 3's right 4": Node(5, Node(3, None, Node(4))),
}
for name, tree in trees.items():
print(name)
print(" children only:", children_only(tree))
print(" with bounds:")
print(" valid:", within_bounds(tree))
print(" in-order:", *in_order(tree, []))5, left 3, 3's right 6
children only: True
with bounds:
5 is inside (-inf, inf)
3 is inside (-inf, 5)
6 is outside (3, 5)
valid: False
in-order: 3 6 5
5, left 3, 3's right 4
children only: True
with bounds:
5 is inside (-inf, inf)
3 is inside (-inf, 5)
4 is inside (3, 5)
valid: True
in-order: 3 4 5The children check said True for both trees. The bounds check reached 6 with the interval from 3 to 5, which 6 lies outside, and returned False; on the second tree 4 fell inside the same interval. The mistake comes from reading the ordering rule as a rule about children, when it is a rule about subtrees: every ancestor of a node, every node on its path up to the root, contributes a bound, and the nearest ancestor on each side gives the tightest one.
The fix costs nothing extra. Each node is still visited once, so the bounds check is O(n), with two numbers passed down per call. An equivalent check uses in-order traversal: a valid binary search tree yields its keys in strictly increasing order, and the broken tree yielded 3 6 5. To spot the mistake in code, look for a validity check whose recursive call passes only the node, with no bounds.
← → move through sections and cards