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?
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.
According to this definition " either 2 children or 0 children for every node"
clearly 0 node with only one child.
A is ans.
@ Debashish Deka
why we are not considering there are only one node in a tree?
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.
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.
Ans: A take n=3, draw a tree and concluded.. :)
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.
Such a binary tree is full binary tree (a binary tree where every node has 0 or 2 children).
yes sir TRUE... working on it :). But this...