Test by Bikram | Data Structures | Test 2 | Question: 2

Question

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$ be $m.$ What is the maximum number of leaves that $T$ can have when root at depth $0$?

• A. $N$
• B. $N * m$
• C. $N^m$
• D. $m^N$

Answer 1

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.