Chapter 29. Binary Trees

A binary tree is a rooted tree in which each vertex has at most two children.

The two children, when present, are usually distinguished as the left child and the right child. This left-right distinction makes a binary tree an ordered rooted tree. It gives binary trees more structure than ordinary rooted trees.

Binary trees are central in computer science because they provide a simple recursive model for search, sorting, parsing, encoding, decision processes, and hierarchical storage.

29.1 Definition

A binary tree is a rooted tree in which every vertex has at most two children.

For each vertex $v$ , its children are assigned positions:

\text{left child of } v

and

\text{right child of } v.

A vertex may have no children, only a left child, only a right child, or both children.

This distinguishes binary trees from unordered rooted trees. In an unordered rooted tree, two children are merely children. In a binary tree, their positions matter.

29.2 Recursive Description

Binary trees have a natural recursive definition.

A binary tree is either empty, or it consists of a root together with two binary trees called the left subtree and the right subtree.

Thus a nonempty binary tree has the form

T = (r, L, R),

where $r$ is the root, $L$ is the left subtree, and $R$ is the right subtree.

Either $L$ or $R$ may be empty.

This recursive description is the basis of most binary tree algorithms.

29.3 Terminology

The standard terminology for rooted trees also applies to binary trees.

Term	Meaning
Root	Distinguished top vertex
Parent	Vertex immediately above another vertex
Child	Vertex immediately below another vertex
Left child	Child in the left position
Right child	Child in the right position
Leaf	Vertex with no children
Internal vertex	Vertex with at least one child
Depth	Distance from the root
Height	Maximum depth of any vertex
Subtree	Tree rooted at a vertex

The left and right positions are part of the structure. A tree with a single left child differs from a tree with a single right child.

29.4 Full Binary Trees

A full binary tree is a binary tree in which every internal vertex has exactly two children.

Thus every vertex has either zero children or two children.

Full binary trees occur in expression trees, parse trees, and branching processes where every internal decision splits into two alternatives.

Theorem 29.1

If a full binary tree has $i$ internal vertices and $l$ leaves, then

l = i + 1.

Proof

Let $n$ be the total number of vertices. Since the tree has $i$ internal vertices and $l$ leaves,

n = i + l.

A tree with $n$ vertices has $n-1$ edges.

In a full binary tree, every internal vertex has exactly two children. Therefore the number of edges is also

2i.

Hence

2i = n - 1.

Substitute $n=i+l$ :

2i = i + l - 1.

Therefore

l = i + 1.

29.5 Complete Binary Trees

A complete binary tree is a binary tree in which every level is full except possibly the last, and the vertices on the last level are placed as far left as possible.

Complete binary trees are important because they can be stored efficiently in arrays.

If the root is stored at index $1$ , then for a vertex at index $j$ :

Relative vertex	Array index
Parent	$\lfloor j/2 \rfloor$
Left child	$2j$
Right child	$2j+1$

This indexing works because the tree has no gaps before the last occupied position.

Complete binary trees are used in binary heaps and priority queues.

29.6 Perfect Binary Trees

A perfect binary tree is a binary tree in which every internal vertex has exactly two children and all leaves have the same depth.

Equivalently, every level is completely filled.

If a perfect binary tree has height $h$ , then level $0$ has $1$ vertex, level $1$ has $2$ vertices, level $2$ has $4$ vertices, and so on.

The number of vertices is

1 + 2 + 2^2 + \cdots + 2^h = 2^{h+1}-1.

The number of leaves is

2^h.

Thus a perfect binary tree grows exponentially with height.

29.7 Balanced Binary Trees

A balanced binary tree is a binary tree whose height is kept small relative to the number of vertices.

Different data structures use different precise definitions of balance. The general purpose is the same: prevent the tree from becoming a long path.

If a binary tree with $n$ vertices has height close to

\log_2 n,

then search and update operations can often be performed efficiently.

If the tree degenerates into a path, its height becomes

n-1,

and these operations may become linear in $n$ .

Balanced binary trees include AVL trees, red-black trees, weight-balanced trees, and treaps.

29.8 Binary Search Trees

A binary search tree is a binary tree whose vertices store keys from an ordered set.

For every vertex with key $k$ :

Region	Key condition
Left subtree	Keys less than $k$
Right subtree	Keys greater than $k$

Variants may allow equal keys by assigning them consistently to one side or by storing counts.

The binary search tree property supports efficient search.

To find a key $x$ , compare $x$ with the root key:

Comparison	Next step
$x = k$	Search succeeds
$x < k$	Search left subtree
$x > k$	Search right subtree

The number of comparisons is bounded by the height of the tree.

29.9 Traversals

Binary trees have several standard traversal orders.

Preorder Traversal

Visit the root, then the left subtree, then the right subtree.

\text{root},\ L,\ R

Preorder traversal is useful for copying a tree or writing prefix notation.

Inorder Traversal

Visit the left subtree, then the root, then the right subtree.

L,\ \text{root},\ R

In a binary search tree, inorder traversal visits keys in sorted order.

Postorder Traversal

Visit the left subtree, then the right subtree, then the root.

L,\ R,\ \text{root}

Postorder traversal is useful when a vertex must be processed after its children, such as when deleting a tree or evaluating certain subexpressions.

Level-Order Traversal

Visit vertices by increasing depth.

Level-order traversal is breadth-first traversal applied to the tree.

29.10 Expression Trees

Binary trees naturally represent expressions with binary operators.

For example, the expression

(a+b)(c-d)

may be represented by a tree whose root is multiplication, whose left subtree represents $a+b$ , and whose right subtree represents $c-d$ .

Leaves store operands. Internal vertices store operators.

Different traversals produce different notations:

Traversal	Expression notation
Preorder	Prefix notation
Inorder	Infix notation
Postorder	Postfix notation

Thus binary trees connect algebraic syntax with computation.

29.11 Decision Trees

A binary decision tree is a binary tree in which each internal vertex represents a yes-no test.

The left and right branches correspond to the two possible outcomes. Leaves represent final decisions, classifications, or outputs.

Binary decision trees appear in algorithms, machine learning, diagnostics, games, and search procedures.

The depth of a leaf represents the number of tests needed to reach that outcome.

A shallow tree gives quick decisions. A deep tree may represent a more complex decision process.

29.12 Height Bounds

A binary tree of height $h$ has at most

1 + 2 + 2^2 + \cdots + 2^h = 2^{h+1}-1

vertices.

Equivalently, if a binary tree has $n$ vertices and height $h$ , then

n \leq 2^{h+1}-1.

Solving for $h$ , every binary tree with $n$ vertices satisfies

h \geq \lceil \log_2(n+1) \rceil - 1.

This lower bound is achieved by perfect binary trees.

At the other extreme, a binary tree with $n$ vertices may have height

n-1,

when every internal vertex has exactly one child.

29.13 External Nodes

Some treatments of binary trees add external nodes to represent empty subtrees.

In this convention, every internal vertex has exactly two children, but some children are marked as external rather than ordinary data-bearing vertices.

This representation is useful in analysis because every missing child becomes an explicit object.

If a binary tree has $n$ ordinary vertices, then it has

n+1

external nodes.

This follows by counting the $2n$ child positions. Among them, $n-1$ are occupied by ordinary edges. The remaining

2n-(n-1)=n+1

positions are empty.

29.14 Binary Trees in Storage

Binary trees can be represented in memory in several ways.

Linked Representation

Each vertex stores:

Field	Meaning
Key or value	Data stored at the vertex
Left pointer	Reference to left child
Right pointer	Reference to right child
Optional parent pointer	Reference to parent

This representation is flexible and works well for dynamic trees.

Array Representation

Complete binary trees can be stored compactly in arrays.

The parent-child relations are computed from indices, so no explicit pointers are needed.

This representation is efficient for heaps because insertions and deletions preserve near-completeness.

29.15 Summary

A binary tree is a rooted tree in which each vertex has at most two children, distinguished as left and right.

Binary trees are recursive objects. A nonempty binary tree consists of a root, a left subtree, and a right subtree.

Important subclasses include full, complete, perfect, balanced, and binary search trees. Each subclass imposes a different structural condition.

Binary trees are fundamental in computer science because they support efficient search, hierarchical representation, expression evaluation, decision procedures, and compact storage.