My algorithm book states that any n-vertex binary tree T can be partitioned by j

Question

My algorithm book states that any n-vertex binary tree T can be partitioned by just removing a single edge into two disconnected trees A and B where neither of them has more than 3/4 of the vertices.

It sounds like it should be simple to create such a tree, but I can't imagine one, my bisections are always better balanced. Can somebody show me a tree where the vertex distribution of 3/4 to 1/4?

This is from "Introduction to Algorithms" by Thomas Cormen, 3rd edition, MIT Press. Appendix B, Problems B-3.

Explanation / Answer

Nobody said that 3/4 was the optimal number. In fact, it seems like 2/3 might be achievable. Starting at the root, consider a walk which always chooses the child with the larger subtree. Consider the first time that you reach a node whose subtree contains less than 2/3 of the nodes. Its parent's subtree contains more than 2/3 of the nodes, so the subtree rooted at its larger child contains at least 1/3 of the nodes. So we have found a node whose subtree contains between 1/3 and 2/3 of the nodes.

Considering the tree with one root and two children, we see that we can't in general obtain a better balanced partition.

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.