# Chapter 29. Binary Trees

# 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.