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

1 votes
1 votes
I think answer is a that is zero because if a node has only one child the number of descendent will become even as every node is considered its own descendent. So every node either contain 2 child or zero child ( leaf node)
1 votes
1 votes
READ QUESTION VERY CAREFULLY :

2 main lines 1)Every Node has odd number of descendants(Childs)

2)Every node considered to be its own descendants(Parent will be considered as it's own child)

As this is binary tree ,Only 2 cases will be possible.

1.Parent with No child (In this case 1(odd) descendants , which is parent itself).

2.Parent with 2 Childs (In this case 3(odd) descendants (1 Parent +2 Child).

NO NODE WILL BE WITH 1 CHILD SO ANSWER IS 0.
Answer:

Related questions

73 votes
73 votes
10 answers
9
go_editor asked Apr 21, 2016
26,925 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
10
go_editor asked Sep 30, 2014
6,578 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
12
go_editor asked Feb 12, 2015
29,999 views
A binary tree T has $20$ leaves. The number of nodes in T having two children is ______.