Final answer:
To find the overhead fraction for a binary tree where internal nodes contain two pointers and leaf nodes contain data, the overhead is the space taken by pointers (8i) over the total space (17i + 9), simplifying towards 8/17 for large trees.
Step-by-step explanation:
To compute the fraction of the total space taken up by overhead in this binary tree node implementation, we consider the space for pointers and data. Internal nodes have two pointers, each 4 bytes, for a total of 8 bytes per internal node with no data field. Leaf nodes have a single data field of 9 bytes with no pointers. A Full binary tree has a property where the number of leaf nodes is one more than the number of internal nodes (if the number of internal nodes is i, the number of leaf nodes is i+1).
In such a tree, if we have i internal nodes, the total number of nodes is 2i + 1. The total space taken by internal nodes is 8i bytes (8 bytes per node), and the total space taken by leaf nodes is 9(i + 1) bytes. Therefore, the total space is 8i (for internal nodes) + 9(i + 1) (for leaf nodes), which simplifies to 17i + 9. The overhead is the space taken by pointers: 8i bytes for internal nodes since leaf nodes have no pointers. So the fraction representing overhead is 8i / (17i + 9).
To simplify this fraction in the lowest terms, we need to divide both the numerator and the denominator by the greatest common divisor of 8i and 17i + 9. Since 8i and 9 do not have a common divisor other than 1, the greatest common divisor is i which leaves us with 8 / (17 + 9/i). As i increases (for larger trees), the 9/i term becomes negligible, so the fraction tends towards 8/17 for very large trees.