# Is this the right strategy to convert an in-level order binary tree to a doubly linked list?

So I recently came across this question - Make a function that converts a in-level-order binary tree into a doubly linked list. Apparently, it's a common interview question.

This is the strategy I had - Simply do a pre-order traversal of the tree, and instead of returning a node, return a list of nodes, in the order in which you traverse them. i.e return a list, and append the current node to the list at each point. For the base case, return the node itself when you are at a leaf.

so you would say

``````left = recursive_function(node.left)
right = recursive_function(node.right)
return(left.append(node.data)).append(right);`
``````

Is this the right approach?

• Thats the basics. But usually the question is about re-linking the current tree (not creating a new list). So you need to modify the current left and right pointers in place so when the processes is finished the data structure has been converted from a tree into a list (in the correct order). So rather than using append (or by writing your version of append) you need to show how to link the current node together with the branches. Commented Sep 20, 2011 at 15:43
• PS. As a hint (make the list circular to make it easier). Commented Sep 20, 2011 at 15:46

Turns out it is:

EDIT: Simplified base case

I implemented the code in Java, it looks like this:

``````public DLLNode treeToList(TreeNode node, DLLNode list)
{
if (node.isLeaf())
return new DLLNode(node.data);

DLLNode left = treeToList(node.left, list);
DLLNode right = treeToList(node.right, list);

DLLNode ret = new DLLNode();

ret.prev = left;
ret.next = right;
ret.data = node.data;

return ret;
}
``````

DLLNode is simply defined with public attributes `DLLNode prev, DLLNode next, int data`, and TreeNode is defined with public attributes `TreeNode left, TreeNode right, int data`. The constructors that I defined, and the `isLeaf()` function are obvious.

Notes: The code does a postorder traversal, not preorder as I thought.

• Usually the question is not to create a new list but to re-link the current tree so that the left and right pointers form a list rather than a tree. PS. You are only linking ret into the list (you are not connecting the lists to ret) Commented Sep 20, 2011 at 15:46
• How are left.next and right.prev defined? Why are list.prev and list.next never modified in your method? Commented Sep 21, 2011 at 20:03

Top and tail with a script tag

``````// load as html page.
// this will write "c1 b1 c2 a1 c3 b2 c4" to the browser

// test data
var c1 = {data: "c1"};
var c2 = {data: "c2"};
var c3 = {data: "c3"};
var c4 = {data: "c4"};
var b1 = {data: "b1", left: c1, right: c2};
var b2 = {data: "b2", left: c3, right: c4};
var a1 = {data: "a1", left: b1, right: b2};

// production function
var llist = function walktree(node)
{
if ( node.left !== undefined)
{
l = walktree(node.left );
node.prev = l.tail;
l.tail.next = node;
}
else
{
}
if ( node.right !== undefined)
{
r = walktree(node.right );
tail = r.tail;
}
else
{
tail = node;
}