recategorized by
35,880 views
43 votes
43 votes

A binary tree $T$ has $n$ leaf nodes. The number of nodes of degree $2$ in $T$ is

  1. $\log_2 n$
  2. $n-1$
  3. $n$
  4. $2^n$
recategorized by

6 Answers

Best answer
86 votes
86 votes

In Binary Tree a node can have at most $2$ children.

Total number of node $\mathbf{N} =$ node with $0$ child $+$ node with $1$ child $+$ node with $2$ child.

$\implies N= n_0 + n_1 + n_2 ($here, in question it is given that no. of leaf nodes i.e no. of nodes with $0$ children is $n$ so $n_0 = n)$

$\implies N=n + n_1 + n_2$

Total number of edges $e=N-1,$ and also $e = n \ast 0+ n_1 \ast1 + n_2 \ast 2$

$\therefore N-1 = n \ast 0+ n_1 \ast1 + n_2 \ast 2$

$\implies n + n_1 + n_2 - 1 = n_1 \ast1 + n_2 \ast 2$
 
$\implies \mathbf{n_2 = n -1}$

Option B is answer.

NOTE - For the tree, the degree of a node is defined as the number of sub-trees of the node or no of children of a node.

edited by
5 votes
5 votes

No of nodes with degree 2 in a  Binary tree = no. Of leaf nodes-1

So Ans = n-1

3 votes
3 votes
Here in question there are few inconsistency.

Assumption 1: here we will strictly talk about complete binary tree ( complete binary tree means a node can have either 0 or 2 child basically node with single child is out of consideration)

Assumption 2: Here by degree 2 it is considered as node with 2 children. ( In general it is not so for internal node of binary tree can have atmost 3 degree 2 of child and 1 of parent)

So if above 2 statements are filled. we can say a general statement that such an tree of n leaf nodes are there then number of internal node will always be n-1.

And say we are considering assumption 2 then all n-1 node will have exactly 2 children thus n-1 is most suitable answer.
Answer:

Related questions

25 votes
25 votes
3 answers
1
Kathleen asked Oct 8, 2014
3,638 views
What is the number of binary trees with $3$ nodes which when traversed in post-order give the sequence $A, B, C ?$ Draw all these binary trees.
26 votes
26 votes
3 answers
2
49 votes
49 votes
7 answers
3
Kathleen asked Oct 8, 2014
38,083 views
The postfix expression for the infix expression $A+B*(C+D)/F+D*E$ is:$AB + CD + *F/D +E*$$ABCD + *F/DE* ++$$A * B + CD/F *DE ++$$A + *BCD/F* DE ++$
23 votes
23 votes
7 answers
4
Kathleen asked Oct 8, 2014
4,946 views
The rank of the following $(n+1) \times (n+1)$ matrix, where $a$ is a real number is $$ \begin{bmatrix} 1 & a & a^2 & \dots & a^n \\ 1 & a & a^2 & \dots & a^n \\ \vdots ...