I have a set of leaf-labeled trees. I want to concatenate them into a single leaf labelled tree in such a way that the height of the resulting tree is smallest possible. Can somebody please help me to generate an algorithm for this task, with good performance?

Leaf labelled tree is a tree in which all the data is held at leaves.

  • $\begingroup$ What do you mean by concatenate? $\endgroup$ – Yuval Filmus Aug 21 '17 at 15:34
  • $\begingroup$ I mean merging it. Please see this image. It explains better. scontent.flhr4-2.fna.fbcdn.net/v/t1.0-9/… $\endgroup$ – Sathish Kumar Aug 21 '17 at 15:46
  • $\begingroup$ Further I want to keep the order of leaf labeled trees to be merged, Hope you can shed some light on. $\endgroup$ – Sathish Kumar Aug 21 '17 at 15:48
  • 3
    $\begingroup$ Please edit the question to make it self-contained. Don't use comments to clarify your question; edit the question to include all information in the question, so it reads well for someone who encounters it for the first time. Thank you! $\endgroup$ – D.W. Aug 21 '17 at 16:34

You can solve this using dynamic programming. Given trees $T_1,\ldots,T_n$, for each $1 \leq a \leq b \leq n$ compute the best way of concatenating $T_a,\ldots,T_b$. Details left to you.

  • $\begingroup$ Thank you, I am thinking of calculating the concatenated height for each couple of trees and only concatenating the couple that generates the least amount of height per an iteration, and continue until the end. I do not have to calculate all possibilities in future iterations since I have already calculated them. Do you find any other strategy? $\endgroup$ – Sathish Kumar Aug 21 '17 at 16:45
  • $\begingroup$ Any strategy which works is great. $\endgroup$ – Yuval Filmus Aug 21 '17 at 17:00

Not the answer you're looking for? Browse other questions tagged or ask your own question.