Register

What is the no. of nodes in the tree that has exactly one child?

1,353 views
0 votes
0 votes
In a binary tree with n nodes every node has an odd no. of descendants. Every node is considered to be its own descendant. What is the no. of nodes in the tree that has exactly one child?

(a) 0

(b) 1

(c) (n-1)/ 2

(d) n-1
User Avatar

1 Answer

Best answer
1 votes
1 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.
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
2 answers
1
sripo asked Dec 25, 2018
4,785 views
In a 3-array tree if internal nodes have exactly 3 children,the number of leaf nodes will be __ ?
In a 3-array tree if internal nodes have exactly 3 children,the number of leaf nodes will be __ ? Does it vary for binary tree? What do you mean by internal nodes? Non root node and leaf node?
In a 3-array tree if internal nodes have exactly 3 children,the number of leaf nodes will be __ ?Does it vary for binary tree?What do you mean by internal nodes? Non roo...
User Avatar
1 votes
1 votes
1 answer
3
ShubhamSwarnkar asked Feb 13, 2019
1,035 views
A family has two children. Given that one of the children is a boy, what is the probability that both children are boys?
I was doing this question using conditional probability formula.... i.e P(2/1)=? Probability of 2nd child to be boy given that 1st child is a boy. By formula, P(2/1)=P(2,...
User Avatar
Link Copied!