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?
For Full binary tree of 5 nodes again answer is 0 because of the condition that we have to find the nodes in the tree that have exactly one child. If this condition is not there then there are 3 nodes with odd number of descendants.
We can check it simply by drawing tree.
@Kuljeet Shan im understanding it as :
there are 3 nodes, root, Ln, Rn then,
root is having 3 descendents - (root itself + Ln + Rn) = 3 descendents
Ln = (Ln itself) = 1 descendent
Rn = (Rn itself) = 1 descendent
where am i wrong ?
Actually i explained the question asked by @arya_stark for full binary tree of 5 nodes.
The above answer for original question is absolutely right and ur explanation is right too.
@akshayaK You can simply draw a full binary tree with 5 nodes you will find that there is no node with exactly one child.
And in my first comment i mentioned the condition that is given in the original question above that is we have to find the 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.
cant i consider this case
i mean a node with self loop;
it satisfies the property that every node has odd number of descendant and is its own descendant!!
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.
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).
Ans: A take n=3, draw a tree and concluded.. :)