# GATE2010-10

5.4k views

In a  binary tree with $n$ nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?

1. $0$
2. $1$
3. $\frac{(n-1)}{2}$
4. $n-1$
in DS
edited
33
It is mentioned that each node has an odd number of descendants including node itself, so all nodes must have an even number of descendants 0, 2, 4 so on. Which means each node should have either 0 or 2 children. So there will be no node with 1 child. Hence 0 answer.
0
Is descendant same as child ?? Does this question means every node is considered as its own child ?? somebody please clarify.
0
What does descendants mean here
0
Descendant of a node is [1(itself) + no. of its children] because children of a node are descendants of that node.
3
yes, here descendent doesnot mean "number of childs"

Number of child + node itself= number of descendents.

Now number of descendents are odd

So, we know Odd=1+Even

So, number of childs is always even
0

@srestha

Yup. the number of children of a node is always even. So $0$ should be the answer.

0

$0$ because every node has an odd number of descendants so least odd number $1$ and every node is considered to be its own descendant so all nodes have even number of descendants $(0,2,4,6...)$ so every node has either $0$ children or $2$ children...

edited by
0
here, descendant refers to degree ???
3
descendant  refers to child of a particular node .
2
A descendant of a node N is either N itself, a child of N, a child of a child of N and so on for any number of levels .. We say node N is an ancestor of node M if M is a descendant of N ...
0
What about full binary tree of 5 nodes?
0

For Full binary tree of 5 nodes again answer is 0 because of the condition that we have to find the nodes in the tree that have exactly one child. If this condition is not there then there are 3 nodes with odd number of descendants.

We can check it simply by drawing tree.

0

@Kuljeet Shan im understanding it as :

there are 3 nodes, root, Ln, Rn then,

root is having 3 descendents - (root itself + Ln + Rn) = 3 descendents

Ln = (Ln itself) = 1 descendent

Rn = (Rn itself) =  1 descendent

where am i wrong ?

0

@akshayaK

Actually i explained the question asked by @arya_stark for full binary tree of 5 nodes.

The above answer for original question is absolutely right and ur explanation is right too.

0
then number of node that have exactly one child should be two right (Ln & Rn) ?
0

@akshayaK  You can simply draw a full binary tree with 5 nodes you will find that there is no node with exactly one child.

And in my first comment i mentioned the condition that is given in the original question above that is we have to find the nodes in the tree that have exactly one child.

It is given that , "every node has an odd number of descendants. Every node is considered to be its own descendant.".

For all Nodes,

Total Odd Descendants = 1 (Itself ) + Descendents other than itself

Descendants other than Itself  = Odd - 1 = Even

3
Can't we say root is it's own child.
in binary tree there are 3 cases

1)  0 child      2)  1 child    3) 2 child

if it hv 1 child ( odd )  then no of descendents are  2 ( even ) no this case is invalid

if it hv 0 or 2 child ( even ) then no of descendents are 1 or 2 ( odd ) respectively and this case is valid

so in this only 0 or 2 child are valid and 1 child is invalid

so  number of nodes in the tree that have exactly one child is 0
2
i think you have mistakenly made an an error in he statement it should be

if it hv 0 or 2 child ( even ) then no of descendents are 1 or ****3*****( odd ) respectively and this case is valid

According to this definition " either 2 children or 0 children for every node"

clearly 0 node with only one child.

A is ans.

3
That's what I was going to write :)
0

why we are not considering there are only one node in a tree?

0
the maximum child possible is 3, that is the node itself with it's 2 child

minimum child possible is 1, that is node itself

right?
0

But Prashant Sir,

The correct definition is, In a binary tree, every node should have at most two children.So a node can have 1 child also.

0

cant i consider this case

i mean a node with self loop;

it satisfies the property that every node has odd number of descendant and is its own descendant!!

0

@Gate Fever how can node of tree have self loops . its not graph , its binary tree

Since Odd + Even = Odd

bydefault 1 descendent (odd) which is the node itself.

Now to get odd number of descendents node must have even number of descendents(nodes with 0,2,4,6.... descendents).

If a node has only one child then number of descendents will be even which is contradiction.

So none of such node is possible

Now, for X descendent = y + 1 =even (as y is odd). Hence for making X as odd, we have to add one more child to it. Thus no node is possible with single child and having odd descendant.

It is mentioned that each node has odd number of descendants including node itself, so all nodes must have even number of descendants 0, 2, 4 so on. Which means each node should have either 0 or 2 children. So there will be no node with 1 child. Hence 0 is answer. Following are few examples.

       a
/    \
b      c

a
/   \
b     c
/  \
d    e

Such a binary tree is full binary tree (a binary tree where every node has 0 or 2 children).

## Related questions

1
9.3k views
A hash table of length $10$ uses open addressing with hash function $h(k) = k \: mod \: 10$, and linear probing. After inserting $6$ ... insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above? $10$ $20$ $30$ $40$
2
2.6k views
A hash table of length $10$ uses open addressing with hash function $h(k) = k \mod 10$, and linear probing. After inserting $6$ ... $46, 42, 34, 52, 23, 33$ $34, 42, 23, 52, 33, 46$ $46, 34, 42, 23, 52, 33$ $42, 46, 33, 23, 34, 52$
3
3.7k views
The following C function takes a singly-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank. typedef struct node { int value; struct node *next; } node; Node * ... $q \rightarrow next = NULL; p \rightarrow next = head; head = p$;
A binary tree T has $20$ leaves. The number of nodes in T having two children is ______.