GATE CSE 2010 | Question: 10

Question

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?

• A. $0$
• B. $1$
• C. $\frac{(n-1)}{2}$
• D. $n-1$

Comments

Note to self : It's just a Wordplay type question

---

A descendant of a node is any node that can be reached by traversing downward through one or more links (edges), including its children, grandchildren, and so on .

---

By the given property in the question the tree can be a perfect binary tree or can be full binary tree

it can never be a complete binary tree because it will violate the condition of odd number of decendents !

Answer 1

$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...

Comments

I think that question is indirectly pointing out perfect binary tree. am i right @Sachin Mittal 1 sir?

---

@halfcodeblood no actually it is pointing to full binary tree where every node have 0 or 2 child , Perfect binary tree means nodes have 0 or 2 child and also all levels are full filled so its not considering Full binary tree cases. Hence its safe to say the condition mentioned is pointing to Full binary tree

---

@Rishabh shukla1006 A  node (may be root node here as you said) descendant to itself ... But a node can't be a child to itself . A single node considered as a node with 0 children not 1 child.

Answer 2

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

So answer is A.

Comments

Can't we say root is it's own child.

---

@inderjeet I have same doubt..By this logic ans should be 1.

---

this tells abut descendaants being even  says nothng abut number of children. wrong answer.

Answer 3

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

Comments

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

---

I understood this answer 😊

Answer 4

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

clearly 0 node with only one child.

A is ans.

Comments

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.

---

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!!

 

---

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

Answer 5

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

Answer is A

Answer 6

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.