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…
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?
Show answerHide answer
Correct answer: (B) e = i + 2n
Explanation
For a full binary tree with n internal nodes, e = i + 2n. Example: a full binary tree with 7 internal nodes of depth up to 2 has i = 0 + 1×2 + 2×4 = 10 and 8 leaves at depth 3, so e = 24 = 10 + 2×7.