+1 vote
77 views

Let $T$ be a $N$-ary tree where each internal node of $T$ have at most $N$ children. Let the maximum depth of any node of $T$ is m then what is the maximum number of leaves that $T$ can have when root at depth $0$?

1. $N$
2. $N * m$
3. $N^m$
4. $m^N$

edited | 77 views

+1 vote
Let the tree T is 3 ary tree , means N = 3

Root None

/      |      \         m = 0  => 3^0=1 node

1       2      3        m = 1  => 3^1=3 node

/ | \   / | \   / | \      m = 2  => 3^2=9 node

at depth m , maximum number of nodes 3^m , we can see from this picture.

so if m is the maximum depth of any node of tree T then maximum number of leaves N^m for a N ary tree.
by Veteran (75k points)
selected by