Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  Loki Astari Sep 20 '11 at 15:43
    
PS. As a hint (make the list circular to make it easier). –  Loki Astari Sep 20 '11 at 15:46

2 Answers 2

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.

share|improve this answer
    
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) –  Loki Astari Sep 20 '11 at 15:46
    
How are left.next and right.prev defined? Why are list.prev and list.next never modified in your method? –  Giorgio Sep 21 '11 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)     
{   
    var l, r, head, tail;
    if ( node.left !== undefined)
    {
        l = walktree(node.left );
        node.prev = l.tail;
        l.tail.next = node;
        head = l.head;
    }
    else
    {
        head = node;
    }
    if ( node.right !== undefined)
    {
        r = walktree(node.right );
        node.next = r.head;
        r.head.prev = node;
        tail = r.tail;
    }
    else
    {
        tail = node;
    }
    return { head: head, tail: tail};
}(a1);


// test harness
var llnode = llist.head;
while ( llnode !== undefined)
{
    document.writeln( llnode.data );
    llnode = llnode.next;
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.