# Treeify - Converting Tree Data Structures

Some of the most interesting algorithms in Computer Science are involving trees. They are simple and often leverage recursion. For instance, pre-order traversal of a tree, of any complexity, can be written as follows:

``````void preorder(tree t)
{
if(t == NULL)
return;
printf("%d ", t->val);
preorder(t->left);
preorder(t->right);
}
``````

For a hobby project, I was faced with an interesting problem of converting a flat representation of a tree into a nested data structure. A flat representation of a tree looks like this:

``````0
0
1
1
2
3
2
1
``````

Each number refers to the nesting level within a tree. After conversion to a nested structure, it should look as follows (square brackets is the Python syntax for a list):

``````[ 0,
0,
[ 1,
1,
[ 2,
[ 3 ],
2],
1]]
``````

I expected this algorithm to be fairly easy to find, but I didn’t have much success with Google. So, as any self respecting programmer would, I rolled up my sleeves and wrote a Python implementation:

``````def treeify(cs):
cur = 0
tree = []
stack = [tree]
for c in cs:
if c['level'] > cur:
l = [c]
stack[-1].append(l)
stack.append(l)
elif c['level'] < cur:
while 1:
stack.pop()
cur = stack[-1]
if c['level'] == cur['level']:
break
stack[-1].append(c)
else:
stack[-1].append(c)
cur = c['level']
return tree
``````

I have tried to make the best use of Python lists by treating them like lists in LISP. Basically, both languages treat variables as references to actual data. So the lists are nothing but lists of references. This leads to some very useful properties. For e.g. in the above code:

• cs: Flat tree structure. This is slightly different from our previous example. It is a list with elements which are hash tables or dictionaries of the form {‘level’: 0, …}. This is better if your node contains other data that can be easily stored in a dictionary.

• tree: Nested tree structure. This is what we would finally return back

• stack: A stack of trees. Top of the stack is the lowermost node of the tree where the next item of the same level can be added as its child. Next element is the stack is its parent node and so on. #### Arun Ravindran

Arun is the author of "Django Design Patterns and Best Practices". Avid open source enthusiast. Keen on Python. Loves to help people learn technology. Works as a product manager at Unisys. Find out more about Arun on the about page.

Don't miss any future posts!

Next: ▶   Moving Blogs to Pelican

Prev: ◀   Buying Kesar in Kashmir

Up: ▲   Blog