edited by
30,000 views
35 votes
35 votes
A binary tree T has $20$ leaves. The number of nodes in T having two children is ______.
edited by

12 Answers

Best answer
25 votes
25 votes

In A binary tree if there are $N$ leaf nodes then the number of nodes having 2 children will be N-1

$\text{Proof}:$ 

Key idea is find number of edges using Degree and find number of edges using nodes and equate them

Let $l$ be the number of leaf nodes, $D_1$ be the number of nodes with one child and $D_2$ be the number of nodes with two children.

$\text{Sum of Degrees}, D = 1 \times l + 3\times D_2 + 2\times D_1 - 1 \text{(for root)}$

(Root is having one degree less because it is not having a parent) 

$D= l+ 3D_2+ 2D_1 - 1 \qquad \rightarrow (1)$

$\text{Number of edges}, e= \frac{D}{2} $

$\text{Number of nodes}, n = D_2+D_1+l $

A tree with $n$ nodes has $n-1$ edges so,

$\frac{D}{2} = D_2+D_1+l-1\qquad \to(2)$

From $(1)$ and $(2)$

$\frac{l+3D_2+2D_1-1}{2} = D_2+D_1+l-1$

$\implies D_2 = l-1$

So, the number of nodes in $T$ having two children  $= 20-1 = 19$

selected by
36 votes
36 votes
$\mathbf{19}$

In Binary tree If there are $N$ leaf nodes then the number of Nodes having two children will be $N-1$. So in this case answer will be $20-1$, means $19$.
edited by
27 votes
27 votes

in a binary tree there are 3 types of nodes are possible 1st with 0 child (aka leaf nodes) 2nd, node with 1 child and 3rd, node with 2 children 
suppose no of leaf nodes =k
no ofnodes with 1 child = x
no of nodes with 2 children = y 
so total no of edges = total degree/2
                                = (k+2x+3y-1)/2 = (k+x+y)-1
note - here we are subtracting 1 from  k+2x+3y bcoz of root node.
after solving y = k-1   
so  ans =20-1=19

11 votes
11 votes

The total number of nodes in an m-ary tree is given by

n =  m*i +1 where i denotes the number of internal nodes

here in question m=2(binary tree)

so n=2i+1

Also, n = i+ l

where l= number of leaves in a binary tree

Combining above equations we get
2i+1 = i+ l

i + 1 = l

so i = l-1

Hence, number of internal nodes in a binary tree is number of leaves -1.

Answer : 20-1 = 19 Internal nodes or 19 nodes with 2 children are there in this binary tree.

Note : The Equations used above are provided in Kenneth Rosen Graph Theory chapter.

Answer:

Related questions

72 votes
72 votes
4 answers
2
62 votes
62 votes
4 answers
3
go_editor asked Feb 12, 2015
16,015 views
Consider a complete binary tree where the left and right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is...