# algorithm - Build tree from list of list

I have a list of list look like: {{f,h,i}, {b,e,f,g}, {a,b,c,d}}

I need to build a tree with the rule:

• for each list the first element is the root.
• rest of elements is the children.

for this example the tree look:

`` ab c de f gh i``

can you help me to write algo for this.

Thank!

It's a simple recursive procedure.

1. If the list contains a list, first recursively deal with that list, then replace it with its first element (its root).

2. Now the list contains only letters (representing nodes).

a. Make the first letter a node.

b. Sort the other elements smaller than the first letter. Chain them into a downward-right facing branch, and make the largest one a left child of the first letter.

c. Similarly, sort the other elements larger than the first letter. Chain them into a downward-right facing branch, and make the smallest one a left child of the first letter.

In pseudocode:

``````def make_into_tree(l):
for e in l:
if type(e) == list:
e = make_into_tree(e)

root = e[0]

smaller = sorted(all letters smaller than e[0])
for each s in smaller (except for first):
make s a right child of its predecessor
smaller_root = smaller[0]
make smaller_root left child of root

larger = sorted(all letter larger than e[0])
for each l in larger (except for first):
make l a right child of its predecessor
larger_root = smaller[0]
make larger_root right child of root

return root
``````