Maddox Smith Staff asked 4 years ago

Internal Nodes

Q

1 [Proper Binary Trees] Prove that the number of leaves (e) in a proper binary tree equals that number of internal nodes (i) plus 1, that is e = i + 1. A proper binary tree is defined to be a binary tree in which every internal node has exactly two children. Hint, one approach is to use proof by induction, with the base case being a tree with no internal nodes and hence comprising of a single leaf. The inductive step is to show that if the hypothesis is true for two subtrees, then it must also be true for the tree composed of a root that has those two subtrees as children.