DSA Counting Nodes in a Complete Tree

The problem

A complete binary tree fills every level except possibly the last. The last level fills from the left, with no gaps before the final node.

The task counts the nodes. A tree built from a list holds exactly as many nodes as the list, and the interest lies in how few nodes the count must touch to prove that total.

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

def build_complete(values):
    nodes = [TreeNode(v) for v in values]
    for i, node in enumerate(nodes):
        if 2 * i + 1 < len(nodes):
            node.left = nodes[2 * i + 1]
        if 2 * i + 2 < len(nodes):
            node.right = nodes[2 * i + 2]
    return nodes[0] if nodes else None

for size in [1, 6, 10, 15, 31]:
    tree = build_complete(list(range(1, size + 1)))
    print("built from", size, "values - expected count:", size)

The sizes mix perfect trees and imperfect ones. A perfect tree fills its last level completely. The sizes 15 and 31 are perfect, and 6 and 10 are not.

Intuition: count everything, touch everything

The first idea counts a node by adding one to the counts of its two subtrees. The idea is plainly correct. It also enters every single node, even inside parts of the tree whose shape is already forced.

Completeness forces a lot of shape. A subtree whose leftmost and rightmost paths have equal length has no gap anywhere. Counting such a subtree node by node repeats work that one formula settles.

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

def build_complete(values):
    nodes = [TreeNode(v) for v in values]
    for i, node in enumerate(nodes):
        if 2 * i + 1 < len(nodes):
            node.left = nodes[2 * i + 1]
        if 2 * i + 2 < len(nodes):
            node.right = nodes[2 * i + 2]
    return nodes[0] if nodes else None

def count_every(node, entered):
    if node is None:
        return 0
    entered[0] += 1
    return 1 + count_every(node.left, entered) + count_every(node.right, entered)

tree = build_complete(list(range(1, 32)))
entered = [0]
total = count_every(tree, entered)
print("count:", total)
print("nodes entered:", entered[0])

The plain count enters all 31 nodes of a perfect tree. Yet the tree's two outer paths already prove its size. The optimal solution cashes in that proof.

Brute force: the full recursive count, counted

The brute force is the plain count, kept honest with an entry counter. Every node adds one recursive call for itself and one call per child.

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

def build_complete(values):
    nodes = [TreeNode(v) for v in values]
    for i, node in enumerate(nodes):
        if 2 * i + 1 < len(nodes):
            node.left = nodes[2 * i + 1]
        if 2 * i + 2 < len(nodes):
            node.right = nodes[2 * i + 2]
    return nodes[0] if nodes else None

def count_every(node, entered):
    if node is None:
        return 0
    entered[0] += 1
    return 1 + count_every(node.left, entered) + count_every(node.right, entered)

for size in [10, 15, 31]:
    tree = build_complete(list(range(1, size + 1)))
    entered = [0]
    total = count_every(tree, entered)
    print("size", size, "- count:", total, "nodes entered:", entered[0])

Entered nodes equal total nodes at every size. The brute force can never do better, because entering nodes is all it does. Skipping a proven subtree is the only way to pay less.

The optimal solution: equal spines mean a formula

A spine is a path that always follows the same child down to a leaf. The rule is one sentence: when a subtree's left and right spine heights are equal, the subtree is perfect and holds 2 to the power h, minus 1, nodes for spine height h.

Unequal spines send the count into both children, where the same test runs again. Perfect parts are settled by the formula and never entered. Only the fringe near the last level is walked.

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

def build_complete(values):
    nodes = [TreeNode(v) for v in values]
    for i, node in enumerate(nodes):
        if 2 * i + 1 < len(nodes):
            node.left = nodes[2 * i + 1]
        if 2 * i + 2 < len(nodes):
            node.right = nodes[2 * i + 2]
    return nodes[0] if nodes else None

def spine(node, go_left):
    h = 0
    while node is not None:
        h += 1
        node = node.left if go_left else node.right
    return h

def count_fast(root):
    entered = [0]
    def count(node):
        if node is None:
            return 0
        entered[0] += 1
        left = spine(node, True)
        right = spine(node, False)
        if left == right:
            return 2 ** left - 1
        return 1 + count(node.left) + count(node.right)
    return count(root), entered[0]

for size in [1, 6, 10, 15, 31]:
    tree = build_complete(list(range(1, size + 1)))
    total, entered = count_fast(tree)
    print("size", size, "- fast count:", total, "nodes entered:", entered)

Every count matches its size. The perfect trees settle at their roots after one entry each. The imperfect trees descend, yet still enter far fewer nodes than they hold.

Walkthrough: counting the ten-node tree

The walk applies the spine test node by node. Each printed step shows the two spine heights at one entered node. Equal heights end that branch with the formula.

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

def build_complete(values):
    nodes = [TreeNode(v) for v in values]
    for i, node in enumerate(nodes):
        if 2 * i + 1 < len(nodes):
            node.left = nodes[2 * i + 1]
        if 2 * i + 2 < len(nodes):
            node.right = nodes[2 * i + 2]
    return nodes[0] if nodes else None

def spine(node, go_left):
    h = 0
    while node is not None:
        h += 1
        node = node.left if go_left else node.right
    return h

def count(node):
    if node is None:
        return 0
    left = spine(node, True)
    right = spine(node, False)
    if left == right:
        print("node", node.value, "spines", left, right, "-> perfect, count", 2 ** left - 1)
        return 2 ** left - 1
    print("node", node.value, "spines", left, right, "-> descend")
    return 1 + count(node.left) + count(node.right)

tree = build_complete(list(range(1, 11)))
print("total:", count(tree))

The root descends because its spines differ. Parts below it settle by formula where their spines agree. The total reads 10 from the formula counts plus the descended nodes themselves.

Complexity

The fast count descends along one fringe, and each entered node pays two spine walks of length O(log n), so its time is O((log n) squared). Its recursion stack holds one path, so its extra space is O(log n).

The plain count enters every node, so its time is O(n). Its stack stays at O(log n) on a complete tree, because completeness bounds the height.

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

def build_complete(values):
    nodes = [TreeNode(v) for v in values]
    for i, node in enumerate(nodes):
        if 2 * i + 1 < len(nodes):
            node.left = nodes[2 * i + 1]
        if 2 * i + 2 < len(nodes):
            node.right = nodes[2 * i + 2]
    return nodes[0] if nodes else None

def spine(node, go_left):
    h = 0
    while node is not None:
        h += 1
        node = node.left if go_left else node.right
    return h

def count_fast(root):
    entered = [0]
    def count(node):
        if node is None:
            return 0
        entered[0] += 1
        left = spine(node, True)
        right = spine(node, False)
        if left == right:
            return 2 ** left - 1
        return 1 + count(node.left) + count(node.right)
    return count(root), entered[0]

for size in [15, 31, 63, 127]:
    tree = build_complete(list(range(1, size + 1)))
    total, entered = count_fast(tree)
    print("size", size, "- fast entered:", entered, " plain entered:", size)

A perfect tree of any size costs the fast count exactly one entry. The gap between 1 and 127 is the whole point of the spine test. Imperfect trees cost more, but only along the fringe where the spines disagree.

Edge cases and pitfalls

The empty tree counts zero. The count function returns before any spine test runs on a missing node. A missing node has no spines to compare.

Height conventions cause the classic off-by-one error. This article counts spine height in nodes, so a lone node has height 1 and the formula gives 2 to the power 1, minus 1, which is 1. Mixing an edges-based height into the same formula breaks every count.

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

def build_complete(values):
    nodes = [TreeNode(v) for v in values]
    for i, node in enumerate(nodes):
        if 2 * i + 1 < len(nodes):
            node.left = nodes[2 * i + 1]
        if 2 * i + 2 < len(nodes):
            node.right = nodes[2 * i + 2]
    return nodes[0] if nodes else None

def spine(node, go_left):
    h = 0
    while node is not None:
        h += 1
        node = node.left if go_left else node.right
    return h

def count_fast(root):
    entered = [0]
    def count(node):
        if node is None:
            return 0
        entered[0] += 1
        left = spine(node, True)
        right = spine(node, False)
        if left == right:
            return 2 ** left - 1
        return 1 + count(node.left) + count(node.right)
    return count(root), entered[0]

print("empty tree:", count_fast(None))
print("single node:", count_fast(build_complete([7])))
print("two nodes:", count_fast(build_complete([7, 8])))
print("last level holds one node:", count_fast(build_complete(list(range(1, 17)))))
print("perfect seven:", count_fast(build_complete(list(range(1, 8)))))

The sixteen-node tree is the sharpest case. Its last level holds a single node at the far left. The count still lands exactly, because the descent follows the fringe where the spines disagree.