Given a full binary tree of size $n$, I need to cut the tree into two by choosing an edge and removing it. I want the cutting to be as equal as possible (i.e. the two subtrees have as equal weight as possible).

Can I always cut the tree into two equal subtrees? If not, what is the lower bound for the cut (the smallest size of the smaller subtree)?

What is an algorithm I can use to find this cut?

  • $\begingroup$ What did you try? Where did you get stuck? Did you try working through some examples to see if you can always cut the tree into two equal subtrees? To find the cut, what algorithms have you considered? Have you tried writing code to enumerate all possible trees of size $n$ (for $n=1,2,3,4,5$), find the optimal cut for each tree, and see what is the worst cut possible? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$
    – D.W.
    Mar 16 '17 at 16:10
  • $\begingroup$ Are the weights on edges or nodes? I think you are mixing up "size" and "weight" which is a bit misleading. $\endgroup$
    – ryan
    Apr 5 '19 at 4:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.