edited by
16,094 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

6 votes
6 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
3 votes
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.

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

Answer:

Related questions

73 votes
73 votes
10 answers
1
go_editor asked Apr 21, 2016
26,965 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,585 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,018 views
A binary tree T has $20$ leaves. The number of nodes in T having two children is ______.