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.
Starting with the above tree, while there remains a node v of degree two in the tree, add an edge between the two neighbors of v and then remove v from the tree. How many edges will remain at the end of the process?
- A.
2 * n1 - 3
- B.
n2 + 2 * n1 - 2
- C.
n3 - n2
- D.
n2 + n1 - 2
Attempted by 45 students.
Show answer & explanation
Correct answer: A
Solution outline:
Sum of degrees: n1 + 2 n2 + 3 n3 = 2(n - 1).
Total nodes: n = n1 + n2 + n3. Subtracting from the degree sum yields n1 - n3 = 2, so n3 = n1 - 2.
Behavior of the removal operation:
Removing a degree-2 node v after adding an edge between its two neighbors does not change the number of leaves (degree-1 nodes). A leaf adjacent to v remains a leaf; non-leaf neighbors do not become leaves.
All degree-2 nodes are removed by the process, and nodes of degree one and three from the original tree remain. Therefore the final number of nodes is n1 + n3.
Final number of edges = final nodes - 1 = n1 + n3 - 1. Using n3 = n1 - 2 gives n1 + (n1 - 2) - 1 = 2*n1 - 3. Hence 2*n1 - 3 edges remain.