Question

DEPTH counting starts at 1 at the root.

How many leaves does a 3-ary tree have if its depth is 8? (HINT: see the pattern for a full binary tree of depth n and modify it).

Answer 1

We observe the following for a full 3-ary tree :

• With depth 1, there is just the root.
  • Number of leaves here = 1 = 3⁰

• With depth 2, there is 1 root, plus 3 children (which are also the leaves).
  • Number of leaves here = 3 = 3¹

• With depth 3, each of the 3 nodes of depth 2 have three children each, making a total of 9 children (which are also the leaves).
  • Number of leaves here = 9 = 3²

So, as seen, the general formula for the number of leaves in a full 3-ary tree of depth n, is given by

= 3^{n - 1}

Thus, for n = 8. the number of leaves is given by

= 3^{8 - 1}

= 3⁷

= 2187