Consider the following questions about binary trees a In a b

Consider the following questions about binary trees.

(a) In a binary tree with exactly 15 internal nodes, 10 of them have 2 children, and the other 5 have 1 child. How many leaf nodes are there in the tree?

(b) Generalize your answer for part (a). In a binary tree with x + y internal nodes, where x of them have 2 children, and y of them have 1 child, how many leaf nodes are there?

(c) Prove your answer to part (b). It is recommended you use induction on n.

Solution

(a) We have been given that tree has 15 internal nodes (Branch nodes). 10 of these branch nodes have 2 children each and the rest 5 of the branch nodes have 1 child each. We have to determine the number of leaf nodes in the tree.

We know that for each branch node, the number of leaf nodes are equal to the number of its children. So if a branch node have k children, then number of leaf nodes that we will obtain through that particular branch would be k.

Using this concept, for the 10 internal nodes that have 2 children each, we will get 2 leaf nodes from each of these internal nodes. Therefore, leaf nodes obtained from these 10 internal nodes would be equal to 20. Same way, for the 5 internal nodes that have 1 child each will give us another 5 leaf nodes. Hence, the total number of leaf nodes would = 2*10+5*1 = 25 (ans)

(b) Let us generalize our answer from previous part:

There are total (x+y) internal nodes. x of them have 2 children each, so thesex internal nodes will give us 2x leaf nodes. y of them have 1 child each, so these y internal nodes will give us y leaf nodes.

Therefore, total leaf nodes = 2x+y

(c) Let us consider the base case. For a graph with 2 branch nodes, 1 with 2 children and 1 with 1 child, there will total number of leaf nodes = 2+1 = 3. Therefore, this statement is true for base case.

Inductive hypthesis: Let us say the statement is true for (n+m) brach nodes, where n is the number of branch nodes with 2 children and m is the number of branch nodes with 1 child.

Therefore, Total number of leaf nodes for (n+m) brach nodes = 2n+m

Inductive Step: Let us check for a tree with ((n+1)+(m+1)) branch nodes.

Total number of leaf nodes = 2(n+1)+(m+1) = 2n+2+m+1 = (2n+m)+(2+1)

From inductive step, we know that (2n+m) is the number of leaf nodes for n branch nodes with 2 children and 1 branch node with 1 child and from the base case we saw that (2+1) is the number of leaf nodes with 1 brach node with 2 child and 1 branch node with 1 child, therefore, combining the two, the statement is true for (n+1)+(m+1) branch nodes.

Hence, the statement is true by induction!