Binary Tree Properties, Proved

Notice that S, the number of nodes with one child, cancels out. The relation holds whatever the shape.

All four, checked over every tree

An example proves nothing. The program below generates every binary tree shape up to 7 nodes and checks all four properties on each one.

import math


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


def all_shapes(n):
    """Every binary tree shape with exactly n nodes."""
    if n == 0:
        return [None]
    out = []
    for left_size in range(n):
        for left in all_shapes(left_size):
            for right in all_shapes(n - 1 - left_size):
                out.append(BNode(left, right))
    return out


def size(node):
    return 0 if node is None else 1 + size(node.left) + size(node.right)


def height(node):
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))


def level_counts(node):
    counts = {}

    def walk(current, level):
        if current is None:
            return
        counts[level] = counts.get(level, 0) + 1
        walk(current.left, level + 1)
        walk(current.right, level + 1)

    walk(node, 0)
    return counts


def leaves_and_twos(node):
    if node is None:
        return 0, 0
    if node.left is None and node.right is None:
        return 1, 0
    left_leaves, left_twos = leaves_and_twos(node.left)
    right_leaves, right_twos = leaves_and_twos(node.right)
    twos = left_twos + right_twos + (1 if node.left and node.right else 0)
    return left_leaves + right_leaves, twos


checked = 0
for n in range(1, 8):
    trees = all_shapes(n)
    for tree in trees:
        h = height(tree)
        counts = level_counts(tree)
        # property 1
        assert all(c <= 2 ** level for level, c in counts.items()), "property 1"
        # property 2
        assert size(tree) <= 2 ** (h + 1) - 1, "property 2"
        # property 3
        assert h >= math.ceil(math.log2(n + 1)) - 1, "property 3"
        # property 4
        leaves, twos = leaves_and_twos(tree)
        assert leaves == twos + 1, "property 4"
        checked += 1
    print("n = %d: %4d distinct shapes, all four properties hold" % (n, len(trees)))

print()
print("binary tree shapes checked in total:", checked)
print("every one of them satisfies all four properties")

n = 1:    1 distinct shapes, all four properties hold
n = 2:    2 distinct shapes, all four properties hold
n = 3:    5 distinct shapes, all four properties hold
n = 4:   14 distinct shapes, all four properties hold
n = 5:   42 distinct shapes, all four properties hold
n = 6:  132 distinct shapes, all four properties hold
n = 7:  429 distinct shapes, all four properties hold

binary tree shapes checked in total: 625
every one of them satisfies all four properties

625 trees, every shape that exists up to 7 nodes, and all four properties hold on all of them. The shape counts down the left are the Catalan numbers again.

An assert that never fires proves nothing by itself, so each was planted against while this chapter was written: changing property 4's check to leaves == twos fails at n = 2, and changing property 2's to a strict inequality fails at n = 1.

The properties in examination form

Quick revision

• Level i holds at most 2 to the power i nodes; proved by induction from the root.
• A tree of height h holds at most 2 to the power (h+1) minus 1 nodes, by summing property 1.
• So n nodes need a height of at least ceiling(log2(n+1)) minus 1.
• In any binary tree, leaves = nodes with two children + 1, and the count of one-child nodes cancels out

of the proof.

• All four were checked over every binary tree shape up to 7 nodes: 625 trees, no exceptions.
• The shape counts 1, 2, 5, 14, 42, 132, 429 are the Catalan numbers.

Test yourself

1. State and prove the maximum number of nodes at level i. 2 to the power i. At level 0 it is 1; if level i has at most 2^i nodes then level i+1 has at most twice that, since each node has at most two children, so the result follows by induction.

2. How many nodes can a binary tree of height 4 hold at most? 2 to the power 5 minus 1, which is 31.

3. What is the minimum height of a binary tree with 100 nodes? Ceiling of log2(101) minus 1, which is 7 minus 1, so 6.

4. State the relation between leaves and nodes with two children, and say what cancels in the proof. Leaves equal nodes with two children plus one. The number of nodes with exactly one child cancels out, so the relation holds whatever the shape.

5. Why is checking every shape up to 7 nodes stronger than checking one example? Because a single example may satisfy a property by accident. Checking all 625 shapes leaves no shape of that size on which the property could fail.

6. Why does an assertion that never fires prove little on its own? Because a check that cannot fail is not a check. Each was planted against: breaking property 4's test fails at n = 2 and breaking property 2's fails at n = 1, which shows the checks can detect a fault.