B.5-3

B.5-3 Show by induction that the number of degree-2 nodes in any nonempty binary tree is 1 fewer than the number of leaves. Conclude that the number of internal nodes in a full binary tree is 1 fewer than the number of leaves.

Let l(T) be the no of leaves and d(T) be the nodes of degree 2(nodes that have 2 children.) of a tree T.
Base:If T is a binary tree with 1 node, then T consists of a single leaf, and no other nodes. In particular, it has no degree 2 nodes. So in this case l(T) = d(T) + 1. d(T) is zero.
Induction hypothesis: Suppose then that n0 is a positive integer with the property that if T is any binary tree with $n > n0 \geq 1 $ nodes, then l(T) = d(T) + 1.
Induction step: Suppose now that T is a binary tree with $n = n0 + 1 \geq 2$ nodes. Then T has a leaf L. By deleting L from T, we get a new tree T' with$ n = n0 \geq 1 nodes$. So by the induction hypothesis, l(T') = d(T') + 1. We consider two cases:
(a) L has no sibling in T, and
(b) L has a sibling in T.
Note that since T has at least two nodes, L is not the root of T, and hence L has a parent P in T. In case (a), P has degree 1 in T, and hence it’s a leaf of T'. Thus, l(T) = l(T') and d(T) = d(T'). So in this case, we have l(T) = d(T) + 1. In case (b), P has degree 2 in T, and hence degree 1 in T'. Thus l(T) = l(T') + 1 and d(T) = d(T') + 1. So by the induction hypothesis, we have that l(T) = l(T') + 1 = d(T') + 1 + 1 = d(T) + 1. the case b proves for full binary. A full binary tree every node has o or two children.