edited by
16,072 views
57 votes
57 votes

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$
edited by

12 Answers

Best answer
58 votes
58 votes
$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
20 votes
20 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.

15 votes
15 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
7 votes
7 votes

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

clearly 0 node with only one child.

A is ans.

Answer:

Related questions

73 votes
73 votes
10 answers
1
go_editor asked Apr 21, 2016
26,929 views
A hash table of length $10$ uses open addressing with hash function $h(k) = k \: \mod \: 10$, and linear probing. After inserting $6$ values into an empty hash table, the...
23 votes
23 votes
3 answers
2
go_editor asked Sep 30, 2014
6,582 views
A hash table of length $10$ uses open addressing with hash function $h(k) = k \mod 10$, and linear probing. After inserting $6$ values into an empty hash table, the table...
35 votes
35 votes
12 answers
4
go_editor asked Feb 12, 2015
30,005 views
A binary tree T has $20$ leaves. The number of nodes in T having two children is ______.