Discrete Mathematical Structures by Pearson

Trees 11-7

11.2.2 Complete Binary Tree

If every internal vertex (node) of a rooted tree has exactly m offsprings (children), then the tree is

called a complete m-ary tree. In particular, if m = 2, then the tree is called complete binary tree.

Figure 11.5 shows a three level binary tree with 15 vertices.

Level vertices

1 2

2 4

3 8

Figure 11.5 Complete binary tree of height 3

v

8

v

9

v

10

v

11

v

12

v

13

v

14

v

6

v

5

v

2

v

4

v

7

v

3

v

1

v

0

Level 1

Level 0(Root)

Level 2

Level

3

The number of vertices in levels 1, 2, and 3 are 2, 4, and 8, respectively, i.e., 2, 2

2

, 2

3

. This

shows that the maximum number of vertices at level k will be 2

k

.

Example 1 A tree has three vertices of degree 2, ...