Use structural induction to show that l(T), the number of leaves of a full binary tree T, is 1 more than i(T), the number of internal vertices of T, where an "internal vertex" is one with children. Which is the correct basis step? Suppose Ti and T are disjoint full binary trees
i(T) + 1
Let T + T1 + T2
T's leaves are those of Ti plus those of T2, so I(T) = I(T1) + I(T2). T's internal vertices are its root plus the internal vertices of T1 and T2, so i(T) 1(T) = i(T1) + i( T2).