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

Check: https://gateoverflow.in/8059/gate2015-2-10

Answer 1

T has 200 leaf which mean 199 internal node hence X=199

Answer 2

Intuitively if you see, while building a binary tree,

At first, the root can contribute to 2 leaves.

After that, converting each leaf to a non-leaf, the effective contribution to increasing leaf node is (degree – 1). Because while it is adding “degree” number of leaves, it itself is converting to an inner node.

Therefore, subsequently, after the root, each node of degree 2 contributes only 1 leaf node to the tree.

Therefore, taking 

L= no. of leaves, and

I = no of inner nodes with degree 2,

L = I + 1 (since root contributes 2 leaves).

I = L – 1 = 200 – 1 = 199.

 

 

You can check out by drawing in a paper how adding one child to a leaf node keeps the overall number of leaf nodes constant. Adding two children, however, increases the number of leaves by 1. 

Answer 3

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

GATE CSE 2015 Set 2 | Question: 10 - 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.

binary tree T that has 200 leaf nodes.

So, number of nodes having exactly 2 children is 199. 

Answer 4

A binary tree made of a leaf node = L + internal node  = I (a node which contain leaf node

Therefore,

Total node = I +L where {l = total internal node and l = total leaf node}; ------ (1)

In Q they ask how many internal node that contain 2 child

Total node = I.2 + 1 --------(2)

where {I =  internal node that  contain exactly 2  child node  And 1 = root node}

In binary tree total internal node is just less than 1 of inyernal node ,L -1 = I;

Internal node = 200 -1 = 199;

equate equation 1 and 2.

I + L = I.2 +1

199 + 200 = i.2 + 1

i = 199.