# Merge Leaf labeled trees [closed]

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.

## closed as unclear what you're asking by xskxzr, dkaeae, Evil, vonbrand, David RicherbyAug 14 at 13:11

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• What do you mean by concatenate? – Yuval Filmus Aug 21 '17 at 15:34
• I mean merging it. Please see this image. It explains better. scontent.flhr4-2.fna.fbcdn.net/v/t1.0-9/… – Sathish Kumar Aug 21 '17 at 15:46
• Further I want to keep the order of leaf labeled trees to be merged, Hope you can shed some light on. – Sathish Kumar Aug 21 '17 at 15:48
• 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! – 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.