Question

Prove that for any non -empty binary tree t if n0 be number of leaves and n1 be the number of nodes of degree 2 then n0=n1+1

Answer 1

Answer:

.

Step-by-step explanation:

The proof is by induction on the size n of T . Let L(T) = No of leaves & D2(T)= No of nodes of T of degree 2 To Prove D2(T)=L(T)-1  Basic Case : n=1 , then T consists of a single node which is a leaf .  L(T)=1 and D2(T)=0 So D2(T)=L(T)-1  Induction Step : Let n > 1 and assume for all non empty trees T1 of size k1 , at least one of x=left(T) or y=right(T) is non empty Assume x is non empty ; the other case is symetric By the induction hypothesis ,  D2(x) = L(y)-1 IF y is empty , then again by the induction hypothesis , D2(y) =L(y)-1 and D2(T) =D2(x)+D2(y)+1 =L(x)-1+L(y)-1+1 = L(x)+L(y)-1  D2(T) = L(T)-1