edited by
3,241 views
6 votes
6 votes

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$ ?

  1. $1/N$
  2. $N-1/N$
  3. $1/K$
  4. $K-1/K$
edited by

3 Answers

6 votes
6 votes

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}$

1 votes
1 votes
$\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}}$
edited by
0 votes
0 votes
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:

Related questions

2 votes
2 votes
3 answers
1
4 votes
4 votes
3 answers
2
Satbir asked Jan 13, 2020
2,872 views
Convert the pre-fix expression to in-fix $- ^{\ast} +ABC^{\ast} – DE+FG$$(A-B)^{\ast}C+(D^{\ast}E)-(F+G)$$(A+B)^{\ast}C-(D-E)^{\ast}(F+G)$$(A+B-C)^{\ast}(D-E)^{\ast}(F+...
5 votes
5 votes
3 answers
3
Satbir asked Jan 13, 2020
5,704 views
The minimum height of an AVL tree with $n$ nodes is$\text{Ceil } (\log_2(n+1))$$1.44\ \log_2n$$\text{Floor } (\log_2(n+1))$$1.64\ \log_2n$