GATE CSE 2015 | Set 3 | Question: 25

Question

Consider a binary tree T that has $200$ leaf nodes. Then the number of nodes in T that have exactly two children are ______.

Comments

Number of leaf nodes (L) = Number of degree 2 nodes (N2​) + 1

holds true only for full binary trees, not for arbitrary binary trees.

proof:- 

in a full binary tree, all nodes are either having two children or 0 children.

let n be the total no of nodes, L be the no.of leaf nodes and N2 be the internal nodes or nodes having two children.

n = L + N2

now, in a tree no of edges = n-1 

or,   n -1 =  2 (N2)  + L 

on simplifying we get, L=N2​+1

no of leaf nodes = no. of internal nodes (having two children )  + 1.

---

In a binary tree, suppose we have 7 nodes in total and 4 leaf nodes.
That means the remaining 3 nodes are internal nodes.

Since each internal node has exactly 2 children, the structure satisfies the binary tree property.

From this, we can conclude the relation:

Number of internal nodes=Number of leaves−1
so ans for this   
200-1=199

---

adding 1 node internal node having 2 childrens increases the overall number of leaf nodes by 1 in a binary tree [you can draw the tree and notice it by yourself easily ] 

 

if i add "N" nodes internal nodes of degree 2 in a binary tree , then number of leaf nodes will be N+1 

 

here, N+1 = 200, then N  = 199 

 

NOTE --> adding a node with degree 1 in a binary tree does not changes # of leaf nodes as - 

previously, assume you have "x" leaf nodes , 

you added 1 node with degree 1, so that leaf become internal with degree 1 child and that child node became a leaf node 

overall leaf node = x + (-1+1) = x only 

Answer 1

L= no of leaf nodes, i1= internal node1 with child, i2= internal node2 with child
Formula:
                      [ L= i2+1 ]
so here L=200 then,
                                 200=i2+1
                                   i2=199
So number of nodes in T that have exactly two children are 199.

Answer 2

Formula: L = M + 1 
where L is leaf nodes 
M is no.of degree 2 nodes 

so ans is 199