Question

A tree is called a (full) m - ary tree if every internal vertex has exactly m children.

An m - ary tree with m = 2 is called a binary tree.
Let T be a 9vertex binary tree.

(a) Find
(i) the number of edges of T;
(ii) the number of leaves of T;
(iii) the number of internal vertices of T.

Answer 1

A 9-vertex binary tree has 8 edges, 5 leaves, and 4 internal vertices.

Step-by-step explanation:

A 9-vertex binary tree can be characterized by several properties:

1. The number of edges in a tree is always one less than the number of vertices, so a tree with 9 vertices (T) has 8 edges.
2. In a binary tree, the number of leaves (L) can be found using the formula L = I + 1, where I is the number of internal vertices. Since T is a binary tree, and there's a total of 9 vertices, if we assume I is the number of internal vertices, then the formula for a binary tree gives us L = 9 - I. Plugging in the number of internal vertices into this equation (which we'll find next) will give us the number of leaves.
3. Each internal vertex has exactly 2 children in a binary tree. If we subtract 1 from the total number of vertices, which accounts for the root, the remaining 8 vertices are divided evenly among the internal vertices, giving us I = 8 / 2 = 4. Therefore, there are 4 internal vertices in T. Using the aforementioned formula, L = 4 + 1, hence there are 5 leaves.

Thus, the 9-vertex binary tree T has 8 edges, 5 leaves, and 4 internal vertices.