GATE CSE 2015 Set 2 | Question: 10

Question

A binary tree T has $20$ leaves. The number of nodes in T having two children is ______.

Comments

Similar question

https://gateoverflow.in/8428/gate2015-3_25

---

No. of full nodes(max degree nodes) == No. of leaves - 1

Answer 1

we can also divide the leaf nodes as 20=16+4

and then can find out the total nodes that are required to reach  to 16 leaf nodes  and 4 leaf nodes from a single root

                 

            

Answer 2

Level 0 = 1 node, Level 1 = 2 nodes, Level 2=4 nodes, Level 3=8 nodes, Level 4=16 nodes, Level 5=32 nodes.

So, level 4 alone cannot give us 20 leaves, but level 5 if taken wholely will give 32 leaves but we need only 20.

So, we need some nodes of level 4 to have children and other nodes to not have children and stay as leaves.

The equation for it will be:

(16-x)*2 +x = 20

or, x = 4

so all nodes till level 3 have two children each to their full capacity and therefore 1+2+4+8 = 15 nodes have two children each till level 3.

Now, 4 nodes in level 4 will have children too, making the count of nodes with two children = 15+4 = 19.

Answer 3

We can also use the formula :

L = (n-1)*I+1

where,

L= leaf nodes

n= n-ary tree

I = Internal nodes

Answer 4

I don’t know why everybody is doing so much calculation this is just a similar question asked 2 times…

GATE CSE 2015 Set 3 | Question: 25 - GATE Overflow

GATE IT 2006 | Question: 9 - GATE Overflow

The tree containing n “degree 2” elements must have n+1 leaf nodes. you can take any counter example and check it never fail.

So, if any tree contain n leaf nodes then n-1 internal nodes have degree 2. just taking complemet of what above said.

In question it is given….

A binary tree T has 20 leaves.

So, number of nodes having 2 children is 19.