ISRO CSE 2020 | Question: 71

Question

Of the following, which best approximates the ratio of the number of nonterminal nodes in the total number of nodes in a complete $K$-ary tree of depth $N$ ?

• A. $1/N$
• B. $N-1/N$
• C. $1/K$
• D. $K-1/K$

Comments

Ratio of number of nonterminal nodes to what?

---

To the total number of nodes.

---

None of answers are good here is an intuitive answer

Answer 1

Considering Full k-ary tree of depth N: (i.e. all nodes present from depth $0$ to $N-1$)

$\frac{Non-Terminal Nodes}{Total Nodes} = \frac{1+k + k^2+...k^{(N-2)}}{1+k + k^2+...k^{(N-1)}}=\frac{k^{(N-1)}-1}{k^{(N)}-1} \cong \frac{1}{K}$

Considering minimally complete k-ary tree of depth N: (i.e. all nodes present from depth $0$ to $N-2$ & one node in depth $N-1$)

$\frac{Non-Terminal Nodes}{Total Nodes} = \frac{1+k + k^2+...k^{(N-3)}+1}{1+k + k^2+...k^{(N-2)}+1}=\frac{k^{(N-2)}-1+k-1}{k^{(N-1)}-1+k-1} =\frac{k^{(N-2)}+k-2}{k^{(N-1)}+k-2} \cong \frac{1}{K}$

So answer will be (c) $\frac{1}{K}$

Comments

Why is 1 added in the denominator when calculating the total number of nodes in a minimally complete k-ary tree?

Since in a k-ary tree a node can have either 0 or k children without violating the definition, shouldn't it be + k instead of +1 at depth (n-1) because minimally k leaf nodes should exist at that level?

Answer 2

$\underline{\textbf{Answer:}\Rightarrow}\;\mathbf{c.}$

For a given $\mathrm{k-ary}$ tree with height $\mathrm N$

Total number of nodes $\mathrm{=\left ( \dfrac{K^{N+1-1}}{K-1} \right )}$

Total Nodes = Non-Leaf Nodes + Leaf Nodes.

Leaf Nodes = $\mathrm{\mathbf{N^{th}}}$ level nodes $\mathrm{=K^N}$

$\therefore $Non Leaf = Total Nodes– Leaf Nodes

$\mathrm{=\dfrac{K^{N+1}-1}{K-1}-K^N = \left ( \dfrac{K^N-1}{K-1}\right )}$

$\therefore \mathrm{\dfrac{Non Leaf}{Total}=\dfrac{\dfrac{K^N-1}{K-1}}{\dfrac{K^{N+1}}{K-1}}}=\dfrac{K^N-1}{K\left (K^N-\dfrac{1}{K}\right )}$

Now, if $\mathrm k\to \infty$, then $\mathrm{K^N-\dfrac{1}{K} = K^N = \dfrac{K^N-1}{K(K^N)} = \dfrac{1}{k}\bigg [1-\dfrac{1}{K^N}\bigg ]\approx \dfrac{1}{K}}$

Answer 3

No. of leaf nodes = no.of non terminal nodes(K-1)+1

no. of leaf nodes = $K^N$

so, no. of non terminal nodes = $\frac{K^N-1}{K-1}$ (Using the above formula)-----1

Total nodes = $\frac{K^N-1}{K-1} +K^N=\frac{K^{N+1}-1}{K-1}$-----2

 Divide 1 and 2 we get approx result $1/K$ (Put N=3 and K=2 you will get the approx result as1/2)

Answer 4

K-array : A rooted tree in which each node have either 0 or K child.

let S be the number of nodes in the tree;

 

Every roted tree have following properties

$indegree=outdegree=S-1$

 

$outdeg(L) + outdeg(I) = S - 1$

$L$ : leaf nodes

$I$: internal nodes

 

we know outgdegree of leaf nodes is 0, so

$K . D^K = S - 1$, let $D^K$ be the number of internal nodes

$D^K = \frac{S - 1}{K}$

 

$ratio = \frac{\frac{S - 1}{K}}{S} = \frac{S - 1}{S . K} = \frac{S (1 - \frac{1}{S})}{K. S} = \frac{(1 - \frac{1}{S})}{K} \approx  \frac{1}{K}$

 

for $S = 1$ it is not defined beacause if tree have only 1 node then it must $0$ outdegree

 

 

 

Answer 5

Ans