Chapter 2: Mathematical Preliminaries );l, 53
Fig. 2.11 Binary tree of minimum height with 9 vertices.
Fig. 2.12 Binary tree of maximum height with 9 vertices.
EXAMPLE 2.1 7
Prove that the number of leaves in a binary tree Tis (/1 + 1)/2, where /1 IS
the number of vertices.
Solution
Let in be the number of leaves in a tree with /1 vertices. The root is of degree
2 and the remaining /1 - in - 1 vertices are of degree 3. As T has /1 vertices,
it has /1 - 1 edges (by Property 4). As each edge is counted twice while
calculating the degrees of its end vertices. 2(/1 - 1) = the sum of degrees of all
vertices = 2 + m + 3(11 - In - 1). Solving for in. we get in = (/1 + 1)12.
EXAMPLE 2.18
For the tree shown in Fig. 2.13, answer the following questions:
(a) Which vertices are leaves and \vhich internal vertices?