The Binary Search Tree: The Invariant

The right way to write the check is the one above: carry a range down the tree. Every node must lie strictly between the bounds it inherits, and it narrows the bound for each child.

The second way to check it

There is a neater test, and it is a direct consequence of chapter 59:

A binary tree is a binary search tree exactly when its inorder traversal is strictly increasing.

class BNode:
    __slots__ = ("data", "left", "right")

    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right


def inorder(node, out=None):
    out = [] if out is None else out
    if node is not None:
        inorder(node.left, out)
        out.append(node.data)
        inorder(node.right, out)
    return out


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


def inorder_increasing(node):
    walk = inorder(node)
    return all(walk[i] < walk[i + 1] for i in range(len(walk) - 1))


impostor = BNode(20, BNode(10, BNode(5), BNode(25)), BNode(30))
genuine = BNode(20, BNode(10, BNode(5), BNode(15)), BNode(30))

for name, tree in (("impostor", impostor), ("genuine ", genuine)):
    print("%s inorder %-22s increasing: %-6s range check: %s"
          % (name, str(inorder(tree)), inorder_increasing(tree),
             whole_subtree(tree)))

print()
print("the two tests agree on both trees:",
      all(inorder_increasing(t) == whole_subtree(t)
          for t in (impostor, genuine)))

impostor inorder [5, 10, 25, 20, 30]    increasing: False  range check: False
genuine  inorder [5, 10, 15, 20, 30]    increasing: True   range check: True

the two tests agree on both trees: True

The impostor's inorder is 5, 10, 25, 20, 30, which is not increasing: 25 comes before 20. That is the same defect seen from a different angle.

Duplicates

The invariant as stated uses strictly less and strictly greater, so duplicates are not allowed. Three conventions exist and an answer should name the one it uses:

Forbid them. An insertion of an existing value does nothing. This is what this book does. All duplicates to the right, using "less than" on the left and "greater than or equal" on the right. Keep a count in each node, which stores one node per distinct value with a multiplicity.

The third is usually the best in practice and is worth mentioning.

What the invariant buys

Everything in the next three chapters. At any node, a comparison tells you which one of the two subtrees can possibly contain your value, so the other is discarded entirely. That is the halving of chapter 50, and it is the whole purpose of the arrangement.

Quick revision

• Binary search tree: at every node, every value in the left subtree is less and every value in the right

subtree is greater.

• "The left child is smaller and the right child is larger" is NOT the invariant: it allows a tree where

a grandchild sits on the wrong side, which search cannot find.

• Check it by carrying a range down the tree, narrowing it at each step.
• Equivalently: a binary tree is a search tree exactly when its inorder traversal is strictly increasing.
• Duplicates are excluded by the strict inequalities; the three conventions are to forbid them, to send

them right, or to store a count per node.

• The invariant is what lets one comparison discard an entire subtree.

Test yourself

1. State the binary search tree invariant exactly. For every node, every value in its left subtree is less than it and every value in its right subtree is greater than it.

2. Why is "the left child is smaller and the right child is larger" wrong? Because it only constrains the immediate children. A grandchild may then sit on the wrong side of an ancestor, as 25 in the left subtree of 20, and a search for it will go the other way and fail.

3. Describe the correct way to check the invariant programmatically. Carry a lower and an upper bound down the tree. Each node must lie strictly between them, and it becomes the upper bound for its left subtree and the lower bound for its right.

4. Give the equivalent test using a traversal. A binary tree is a binary search tree exactly when its inorder traversal is strictly increasing.

5. What is the inorder of the impostor tree in this chapter, and what does it show? 5, 10, 25, 20, 30. It is not increasing, since 25 comes before 20, which shows the tree is not a search tree.

6. Name the three conventions for duplicate values. Forbid them; place them all in the right subtree using a non-strict comparison there; or store a count in each node so one node holds a value and its multiplicity.