0

A ternary tree is an ordered tree where each node has either $0$ or $3$ children. Such a tree is full if all leaves are at the same distance from the root. Derive an explicit formula for the number of leaves and the total number of nodes, in a full ternary tree of height h.

Here's what I know, number of nodes = number of edges + $1$ AND with $i$ internal vertices has $l = (m - 1)i + 1$ leaves. But how exactly do I create an explicit formula for number of leaves and total number of nodes?

f.fans
  • 11

1 Answers1

1

Experiment. First, construct a full ternary tree of height 1: $(u, v_{1}), (u, v_{2}), (u, v_{3})$. Next, a full ternary tree of height 2, etc.. Write down the number of nodes in each tree, and for each tree, the number of nodes at the same distance from the root, for each distance.

avs
  • 6,276