Consider a full binary tree with n internal nodes, internal path length i, and…
2017
Consider a full binary tree with n internal nodes, internal path length i, and external path length e. The internal path length of a full binary tree is the sum, taken over all nodes of the tree, of the depth of each node. Similarly, the external path length is the sum, taken over all leaves of the tree, of the depth of each leaf.
Which of the following is correct for the full binary tree?
- A.
e = i + n
- B.
e = i + 2n
- C.
e = 2i + n
- D.
e = 2^n + i
Attempted by 333 students.
Show answer & explanation
Correct answer: B
Correct relation: e = i + 2n
Proof (by induction on the number of internal nodes n):
Base case: n = 1. The tree has a root (internal node) at depth 0 and two leaves at depth 1. So i = 0 and e = 2, and indeed e = i + 2n = 0 + 2·1 = 2.
Inductive step: Assume every full binary tree with n - 1 internal nodes satisfies e = i + 2(n - 1). Take a full binary tree with n internal nodes. Choose an internal node whose two children are leaves (such a node exists). Let the chosen internal node be at depth d.
Remove its two leaf children and regard the resulting tree. In the original tree those two leaves contributed 2(d + 1) to e, and the parent contributed d to i. After removal the parent becomes a leaf and contributes d to e, and is no longer counted in i.
Let e' and i' be the external and internal path lengths of the smaller tree. Then e = e' + 2(d + 1) - d = e' + d + 2, and i = i' + d. Therefore (e - i) = (e' - i') + 2.
By the inductive hypothesis e' - i' = 2(n - 1). Hence e - i = 2(n - 1) + 2 = 2n, which gives e = i + 2n.
Example: For n = 1, i = 0 and e = 2. For n = 2 (a root, one internal child, and three leaves), you can compute i and e and verify e = i + 2n still holds.