Discussion
Consider a binary tree \(T\) in which every node has either zero or two children. Let \(n \gt 0\) be the number of nodes in \(T\).
Which ONE of the following is the number of nodes in \(T\) that have exactly two children?
Answer: B
The number of nodes with two children is \(\dfrac{n-1}{2}\).
In a full binary tree, let i be the number of internal nodes (two children each) and l the number of leaves. Counting edges two ways: every node except the root has exactly one parent edge, so there are n - 1 edges, and each internal node contributes 2 edges, so there are 2i edges. Hence:
\[ 2i = n - 1 \quad \Rightarrow \quad i = \frac{n-1}{2} \]
A check: a root with two leaf children has n = 3 and i = 1 = (3 - 1)/2. (n + 1)/2 is the number of leaves, the usual confusion, and n/2 or (n - 2)/2 are not even integers for the odd n that a full binary tree always has.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development