Discrete Mathematics for Computer Science

Rooted Trees 381

Of special interest in computer science is the family of rooted trees in which each
vertex has at most two children and the children are ordered by being designated as either
the left child or the right child of the vertex.

Definition 3. A binary tree is either a tree with no vertices or a rooted tree for which
each vertex has at most two children. Each child of a vertex in a binary tree is designated
as the left child of the vertex or the right child of the vertex (but not both).

Normally, a tree may not have an empty vertex set, but in the case of binary trees, the
notion of an empty tree is useful. The leaves of a binary tree are considered to have empty
subtrees for both the left and the right child. This convention gives a convenient way to
determine when a leaf in a binary tree has been reached. The definition of isomorphism for
binary rooted trees includes more than the conditions for isomorphism between two graphs.
For two binary rooted trees T 1 and T2 to be isomorphic, we require, as with any rooted tree,
that the root of T 1 be mapped to the root of '2. We also require one additional property of
the isomorphism of binary rooted trees: If F : V(TI) -+ V(T 2 ) is an isomorphism for two
rooted binary trees T 1 and T 2 , and if w is a left (right) child of v in T 1 , then F(w) must
be a left (right) child of F(v) in T 2 .The fact that each child of a vertex is designated as
either the left or the right child of the vertex means the two binary trees in Figure 6.43(a)

and 6.41(b) are different.

a a

C C

Figure 6.43 Two distinct binary trees.

All binary trees with fewer than five vertices are pictured in Figure 6.44. That is, every
binary tree with fewer than five vertices is isomorphic to one of these binary trees.

nn=3

n=4

Figure 6.44 Binary trees with fewer than five vertices.