# 12.2. Binary Trees¶

## 12.2.1. Definitions and Properties¶

A *binary tree* is made up of a finite set of elements
called *nodes*.
This set either is empty or consists of a node called the
*root* together with two binary trees, called the left and
right
*subtrees*, which are disjoint from each other and
from the root.
(Disjoint means that they have no nodes in common.)
The roots of these subtrees are
*children* of the root.
There is an *edge* from a node to each of its children,
and a node is said to be the *parent* of its children.

If \(n_1, n_2, ..., n_k\)
is a sequence of nodes in the tree such
that \(n_i\) is the parent of
\(n_i+1\) for \(1 \leq i < k\),
then this sequence is called a *path* from
\(n_1\) to \(n_k\).
The *length* of the path is \(k-1\).
If there is a path from node \(R\) to node \(M\),
then \(R\) is an *ancestor* of \(M\), and
\(M\) is a *descendant* of \(R\).
Thus, all nodes in the tree are descendants of the root of the tree,
while the root is the ancestor of all nodes.
The *depth* of a node \(M\) in the tree is the length
of the path from the root of the tree to \(M\).
The *height* of a tree is the depth of the
deepest node in the tree.
All nodes of depth \(d\) are at
*level* \(d\) in the tree.
The root is the only node at level 0, and its depth is 0.
A *leaf node* is any node that has two empty children.
An *internal node* is
any node that has at least one non-empty child.

Figure 12.2.1 illustrates the various terms used to
identify parts of a binary tree.
Figure 12.2.2 illustrates an important point regarding
the structure of binary trees.
Because *all* binary tree nodes have two children
(one or both of which might be empty), the two binary
trees of Figure 12.2.2 are *not* the same.

Two restricted forms of binary tree are sufficiently
important to warrant special names.
Each node in a *full binary tree*
is either (1) an internal node with exactly two non-empty children or
(2) a leaf.
A *complete binary tree* has a restricted shape obtained by
starting at the root and filling the tree by levels from left to
right.
In the complete binary tree of height \(d\), all levels
except possibly level \(d\) are completely full.
The bottom level has its nodes filled in from the left side.

Figure 12.2.3 illustrates the differences between
full and complete binary trees. [1]
There is no particular relationship between these two tree shapes;
that is, the tree of Figure 12.2.3 (a) is full
but not complete while the tree of Figure 12.2.3
(b) is
complete but not full.
The *heap* data structure is an example
of a complete binary tree.
The *Huffman coding tree*
is an example of a full binary tree.

[1] | While these definitions for full and complete binary tree are the ones most commonly used, they are not universal. Because the common meaning of the words "full" and "complete" are quite similar, there is little that you can do to distinguish between them other than to memorize the definitions. Here is a memory aid that you might find useful: "Complete" is a wider word than "full", and complete binary trees tend to be wider than full binary trees because each level of a complete binary tree is as wide as possible. |