The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+22 votes
2.3k 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$
asked in DS by Veteran (101k points)
edited by | 2.3k views
+15
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

9 Answers

+29 votes
Best answer
$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...
answered by Junior (515 points)
edited by
0
here, descendant refers to degree ???
+2
descendant  refers to child of a particular node .
+1
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?
+12 votes

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.

answered by Boss (42.8k points)
+1
Can't we say root is it's own child.
+9 votes
answered by Boss (11.5k points)
+8 votes
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
answered by Active (2.5k points)
+6 votes

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

clearly 0 node with only one child.

A is ans.

answered by Veteran (60.8k points)
+2
That's what I was going to write :)
0

@ Debashish Deka

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.

+4 votes
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
answered by Active (1.9k points)
+3 votes

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.

answered by Active (1.6k points)
+2 votes

Ans: A take n=3, draw a tree and concluded.. :)

answered by Loyal (7.3k points)
0 votes

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

answered by Loyal (8.9k points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,529 questions
46,674 answers
139,827 comments
57,596 users