recategorized by
1,549 views
2 votes
2 votes

____ number of leaf nodes in a rooted tree of $n$ nodes, where each node is having $0$ or $3$ children

  1. $\frac{n}{2}$
  2. $\frac{(2n+1)}{3}$
  3. $\frac{(n-1)}{n}$
  4. $(n-1)$
recategorized by

3 Answers

2 votes
2 votes
For an k-ary tree , where each node has k children or no children,

$L=(k-1)*I+1\;  \;\; \ldots (1) $

Where L= no. of leaf nodes and $I=$  no. of internal nodes.

In the given question tree is a ternary tree having 0 or 3 children to each node.

For such type of full ternary tree every node is either a leaf or internal node.

 $\implies L+I=n\implies I=n-L$

So $L=(3-1)*I+1$        (k=3)

$\Rightarrow L=2*(n-L)+1$

$\Rightarrow L=\frac{2n+1}{3}$
1 votes
1 votes

$n = 7.$

  1. $\frac{n}{2} = \frac{7}{2} = 3.5 $
  2. $\frac{2n+1}{3} = \frac{15}{3} = 5$
  3. $\frac{n -1}{n} = \frac{6}{7} = 0.85$
  4. $(n-1)= 7-1 =6.$

$\therefore$ Option B is correct.

0 votes
0 votes
→ Any n-ary tree in which every node has either 0 or n children will take L=(n-1)*I +1
[ Where L is the number of leaf nodes and I is the number of internal nodes]
→ Given data n=3.
L=(3-1)I +1
=2I +1 ------------> 1
→ To find total number of nodes is nothing but sum of leaf nodes and internal nodes
n=L+I ------------> 2
With the help of 1 and 2, we get L =(2n+1)/3
Answer:

Related questions

1 votes
1 votes
3 answers
1
Arjun asked Dec 7, 2018
1,258 views
The smallest element that can be found in time ____ in a binary max heap.$O(n \log n)$$O( \log n)$$O(n)$$O(n^2)$
5 votes
5 votes
5 answers
2
Arjun asked Dec 7, 2018
2,074 views
______ to evaluate an expression without any embedded function calls.Two stacks are requiredone stack is neededThree stacks are requiredMore than three stacks are require...
1 votes
1 votes
2 answers
3
Arjun asked Dec 7, 2018
3,418 views
For a given hash table $T$ with $10$ slots that stores $1000$ elements, the load factor $\alpha$ for $T$ is$100$$0.01$$200$$1.05$
1 votes
1 votes
1 answer
4
Arjun asked Dec 7, 2018
4,250 views
____ is the worst-case time complexity for all operations (i.e.,) search, update and delete) in a general Binary Search tree$O(n)$$O(n \log n)$$O( \log n)$ for search and...