A binary tree with n > 1 nodes has n1, n2 and n3 nodes of degree one, two and…
2008
A binary tree with n > 1 nodes has n1, n2 and n3 nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors.
n3 can be expressed as
- A.
n1 + n2 - 1
- B.
n1 - 2
- C.
[((n1 + n2)/2)]
- D.
n2 - 1
Attempted by 281 students.
Show answer & explanation
Correct answer: B
The Handshaking Theorem states:
∑ deg(v) = 2 |E|
where |E| is the number of edges.
In a tree with n nodes, the number of edges is always:
|E| = n - 1
Substituting |E| = n - 1 into the Handshaking Theorem:
∑ deg(v)= 2|E| =2(n-1)
Let:
n1 = number of nodes of degree 1
n2 = number of nodes of degree 2
n3 = number of nodes of degree 3
Total nodes:
n=n1+n2+n3
Degree sum equation:
n1 + 2 * n2 + 3 * n3 = 2(n−1)
Substituting n=n1+n2+n3:
n1 + 2 * n2 + 3 * n3 = 2(n1+n2+n3) − 2
Simplifying:
n3=n1−2
Key facts: In any tree with n nodes, the sum of degrees equals 2(n-1).
Write the degree sum: 1*n1 + 2*n2 + 3*n3 = 2(n - 1).
Use n = n1 + n2 + n3 and substitute into the right-hand side: 2(n - 1) = 2(n1 + n2 + n3) - 2.
Set equal and simplify: n1 + 2*n2 + 3*n3 = 2n1 + 2n2 + 2n3 - 2.
Rearrange terms: 0 = n1 - n3 - 2, therefore n3 = n1 - 2.
Final result: n3 = n1 - 2
Thus the correct expression for the number of degree-three nodes is n1 - 2.