Algorithm Problem – Binary Tree to List
Here is an interesting problem i came across. If you are bored (and smart), give it a shot.
Some refreshers, and an example you can use:
An ordered binary tree looks like this:
A circular doubly linked list looks like this:
The problem at hand:
Suggest a recursive algorithm which takes the ordered binary tree and rearranges the internal pointers to make a circular doubly linked list out of it. The “small” pointer should play the role of “previous” and the “large” pointer should play the role of “next”. The list should be arranged so that the nodes are in increasing order. Return the head pointer to the new list.
So here’s your final draft:
Go play.
Hey, nice and thoughtful. My 10 minute solution is as follows:
The way a tree transforms into a linked list is when it just start going to one side. in this case its : 5-4-3-2-1 which is 4 to the left of 5…3 to the left of 4…etc…(you get the point). now the question is how do we go there…
Well we know that from balanced binary trees that when we get a disbalance, we do rotations to make it balanced. (a binary tree which is like 5-4-3-2-1 is the most disbalanced tree right?). Now we have a fairly balanced tree (assumed) so we’ll again do rotations to convert it to a disbalanced, one offshoot tree (like we want to). We write a recursive function (im not putting the implementation here) which will go as deep as finding a tree which is not a disbalanced tree. For example in above picture,,, the 1-2-3 sub tree. well do a rotation on 2…make it 3-2-1 (all in one direction to left). we keep doing it for every subtree that is balanced or not in the required form. and finally we’ll have the required linked list form. Now during that we didnt really do anything about making it a doubly linked list…which is fairly easy making every1’s right pointer point to the parent and the LEFT most node’s right pointer point to the root, point head at that node and there you have a doubly linked list binary tree.
leme know about my solution. and yea, i have something similar at my blog as well. would you like to take a look at : http://zakimirza.wordpress.com/2007/03/25/quiz-2-tree-problem-ds/
zakimirza
March 31, 2007
Zaki, interesting technique!.. besides examining the efficiency of your algorithm would be a subject of another post..its really interesting cause i jus realized that given two different binary search trees on a given set of n keys, it is always possible to transform one tree into the other, using only a sequence of O(n) rotations. However since your recursive function digs into the tree… and now i wanna experiment this with several trees…and pulls out balance trees, converts them into a list, im wondering if the efficiency would be decent.
Nevertheless , its a super perspective.
Your blog is sure good! Great post here! http://zakimirza.wordpress.com/2007/03/28/about-quizes-and-blog/
Nirmal
April 1, 2007
Thank you for appriciating my blog. I think the efficiency in the worst case can be when the three is totally balanced. it would be fun to see how this bahaves on a AVL or redblack. But its gotta be some factor below n for sure. lets c.
zakimirza
April 2, 2007
that asks for another quiz btw
given two differnt trees, convert between them OPTIMALLY. have you worked on graph drawing? this kind of problems arise there sparingly. For example, give a very dense graph, you might want to visualize it in different ways etc.
zakimirza
April 2, 2007
yes, i did have a graph theory course at college, however i’ve not tried many algorithms with graph theory concepts…
an avl and the red-black would be below O(n) i agree…
Nirmal
April 3, 2007
[...] on April 3rd, 2007. Zaki has presented an interesting perspective at the original problem [...]
Binary Tree to List- Solutions.. « the madcap laughs…..
April 3, 2007
The very order 1, 2, 3, 4, 5 indicates that what you require is in in-order. Though I haven’t thought strongly about its exact implmentation, I think this should be possible.
Sunil Jagadish
June 14, 2007
How about the following (based on inorder walk).
// explore returns a circular linked list // at each level.
explore(node):
lnode = explore(node.left)
lnode.left.right = node
node.left = lnode.left
rnode = explore(node.right)
rnode.left.right = lnode
lnode.left = rnode.left
rnode.left = node
node.right = rnode
return lnode
this runs in O(n) and works for a perfectly balanced tree. For an imbalanced tree we’ll need to create self loops if a left/right child is missing. I didn’t test this thoroughly but it seems to work.
amod
May 1, 2008
wt?
ytik ytkyt
August 7, 2008
I think I got a solution from this using Python..
def to_list(tree):
if tree is None:
return None
else:
return [tree.key, tree.left, tree.right]
kristian lejao
February 20, 2009
Oops! Nevermind
kristian lejao
April 19, 2009