Binary Trees

In a general tree, how many children a node will have is unpredictable; this complicates both representation and cost analysis. A binary tree limits branching to at most two: every node can have a left child and a right child, or neither.

The constraint is not merely a simplification. Two children are the natural counterpart of binary decisions in the form of “greater or smaller,” “left or right,” “yes or no”; this is why search trees, decision trees, and expression trees are always binary.

Left and Right Are Separate Information

In a general tree, the order of children is usually meaningless. In a binary tree, though, left and right are separate positions: whether a node’s single child is on the left or the right is part of the structure.

This distinction gains meaning in later lessons: in a search tree, the left carries smaller values and the right carries larger ones; in an expression tree representing subtraction, swapping left and right changes the result.

Shape Classes

Three definitions are commonly used and commonly confused.

Full binary tree: Every node has either zero or two children; no node has a single child.

Complete binary tree: Every level except possibly the last is entirely full, and the nodes on the last level are packed from left to right. A gap can occur only at the right end.

Perfect binary tree: Every level is entirely full; leaves are all at the same depth.

     full but not complete    complete but not perfect      perfect
        (a)                        (a)                    (a)
       /   \                      /   \                  /   \
     (b)   (c)                  (b)   (c)              (b)   (c)
    /   \                      /   \   /              /  \   /  \
  (d)   (e)                  (d)  (e)(f)            (d) (e)(f) (g)

A perfect tree is both full and complete. The concept of a complete tree will be the foundation of the heap structure in later lessons: gaps occurring only at the right end is what makes it possible to fit the tree into an array.

Height and Node Count

In a binary tree, level $d$ holds at most $2^d$ nodes ($d$ being the depth). Two bounds follow from this.

The maximum number of nodes in a binary tree of height $h$:

$$1 + 2 + 4 + \dots + 2^{h} = 2^{h+1} - 1$$

Read in reverse, the minimum height of a tree with $n$ nodes:

$$h \geq \log_2(n + 1) - 1$$

In the worst case, every node has a single child and the height is $n - 1$.

These two bounds quantify the previous lesson’s closing question. A binary tree with one thousand nodes has a height around nine if balanced, and nine hundred ninety-nine if degenerate. Since search cost is proportional to height, the difference between the two is more than a hundredfold.

Linked Representation

The general representation is every node holding two links:

class BinaryNode:
    def __init__(self, value: int) -> None:
        self.value = value
        self.left: "BinaryNode | None" = None
        self.right: "BinaryNode | None" = None


def node_count(node: BinaryNode | None) -> int:
    if node is None:
        return 0
    return 1 + node_count(node.left) + node_count(node.right)


def height(node: BinaryNode | None) -> int:
    if node is None:
        return -1                       # an empty tree's height is treated as -1
    return 1 + max(height(node.left), height(node.right))


def is_full(node: BinaryNode | None) -> bool:
    if node is None:
        return True
    if (node.left is None) != (node.right is None):
        return False                    # a single-child node was found
    return is_full(node.left) and is_full(node.right)


root = BinaryNode(12)
root.left = BinaryNode(18)
root.right = BinaryNode(7)
root.left.left = BinaryNode(25)
root.left.right = BinaryNode(14)

print(node_count(root), height(root))    # 5 2
print(is_full(root))                          # True
root.right.left = BinaryNode(30)                 # a single child added to node 7
print(is_full(root))                          # False

Treating an empty tree’s height as $-1$ is a convention; a single-node tree’s height then comes out to $0$, staying consistent with the definition from the previous lesson.

Array Representation

If the tree is complete, links are not needed at all. Nodes are placed into an array level by level, from left to right; the relationship is computed with index arithmetic:

$$\text{left}(i) = 2i + 1, \qquad \text{right}(i) = 2i + 2, \qquad \text{parent}(i) = \left\lfloor \frac{i-1}{2} \right\rfloor$$

tree = [12, 18, 7, 25, 14, 30]      # complete binary tree, in level order

def left(i: int) -> int: return 2 * i + 1
def right(i: int) -> int: return 2 * i + 2
def parent(i: int) -> int: return (i - 1) // 2

print(tree[0], tree[left(0)], tree[right(0)])       # 12 18 7
print(tree[left(1)], tree[right(1)])                # 25 14
print(tree[parent(5)], tree[parent(4)])             # 7 18

The advantages of this representation are the same as the array discussion in the first topic: there is no pointer overhead, and because nodes sit contiguously, cache behavior is good.

Its constraint is that the tree must be complete. If the tree is sparse — a degenerate chain, for example — the array representation requires $2^{h+1}$ slots and most of it stays empty. For this reason the array representation is used in structures whose shape is guaranteed; the heap is the main example of this.

What “Balanced” Means

The word “balanced” does not have a single definition. Three criteria are common: the difference between subtree heights at every node being bounded, the ratio of subtree sizes at every node being bounded, and leaves being at the same depth.

All three serve the same purpose — keeping height logarithmic — but different structures choose different criteria. All three will appear in later lessons: height difference in AVL trees, black node count in red–black trees, and equal depth in 2-3 trees.

The Number of Binary Trees

A side note shows how varied tree shapes can be: the number of distinct binary tree shapes with $n$ nodes grows quickly — there are five distinct shapes with three nodes and fourteen with four. These numbers are known as Catalan numbers and are the solution to a counting problem: once a root is chosen for $n$ nodes, every way of dividing the remaining nodes between the left and right subtrees produces a distinct shape, so the count grows by roughly a factor of four per node.

The practical consequence is this: the same data set can be stored in very different shapes depending on insertion order, and shape determines cost. Only a small fraction of these shapes are balanced; relying on a random shape means staying exposed to the worst case. This is the rationale behind the concept of balancing.

Summary

• In a binary tree every node has at most two children, and left and right are separate positions.
• A full tree has no single-child node; a complete tree has a gap only at the right end of the last level; a perfect tree has every level full.
• A tree of height $h$ holds at most $2^{h+1}-1$ nodes; the minimum height of an $n$-node tree is logarithmic, and linear in the worst case.
• In the linked representation every node holds two links; an empty tree’s height is counted as $-1$.
• Complete trees can be represented with an array: left $2i+1$, right $2i+2$, parent $\lfloor (i-1)/2 \rfloor$.
• The same data set can be stored in many different tree shapes; shape determines cost.

Next Step

The tree has been built, but it has not yet been traversed. There is more than one way to visit all the nodes of a tree, and which way is chosen determines the ordering obtained. The next lesson takes up the four basic traversal orders and which problem each is used for.