Page 373 - Discrete Mathematics and Its Applications

352 5 / Induction and Recursion

Basis step

Step 1

Step 2

Step 3

FIGURE 3 Building Up Extended Binary Trees.

Binary trees are a special type of rooted trees. We will provide recursive definitions of
two types of binary trees—full binary trees and extended binary trees. In the recursive step of
the definition of each type of binary tree, two binary trees are combined to form a new tree
with one of these trees designated the left subtree and the other the right subtree. In extended
binary trees, the left subtree or the right subtree can be empty, but in full binary trees this is not
possible. Binary trees are one of the most important types of structures in computer science. In
Chapter 11 we will see how they can be used in searching and sorting algorithms, in algorithms
for compressing data, and in many other applications. We first define extended binary trees.

DEFINITION 4 The set of extended binary trees can be defined recursively by these steps:

BASIS STEP: The empty set is an extended binary tree.
RECURSIVE STEP: If T 1 and T 2 are disjoint extended binary trees, there is an extended
binary tree, denoted by T 1 · T 2 , consisting of a root r together with edges connecting the
root to each of the roots of the left subtree T 1 and the right subtree T 2 when these trees are
nonempty.

Figure 3 shows how extended binary trees are built up by applying the recursive step from one
to three times.
We now show how to define the set of full binary trees. Note that the difference between
this recursive definition and that of extended binary trees lies entirely in the basis step.