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

Descendants are not restricted to just immediate children only !!!

---

For further clarification check this: 

Reference: https://www.youtube.com/watch?v=tORLeHHtazM&list=PLBF3763AF2E1C572F&index=6

---

Answer is valid even if we take a single node or 1 node because every node is considered as it’s own descendant and here only 1 node so odd number of descendants satisfying questions criteria.

but it contains no child so number of nodes having single child is 0.

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

here, descendant refers to degree ???

---

descendant  refers to child of a particular node .

---

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

---

What about full binary tree of 5 nodes?

---

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.

---

@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 ?

---

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

---

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

---

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

---

Basically, the question meant, for any node, the node is considered to be its own descendants but cannot be considered its own child. Right?

---

In question, they mention that it is a just binary tree. My doubt is why do you consider a full binary tree instead of there is a chance considering the left/right skewed tree

---

@Chaitanya Sai if you consider left/right skewed then there will be both even number and odd number of descendants possible which is not allowed as per the given ques. 

---

@Chaitanya Sai Can't we say root is it's own child? By this logic ans should be 1?

Please clear my doubt what am I missing..

---

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

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.

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

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