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

Question

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. — Martin York, Sep 20 '11 at 15:43

ankit · Answer 1 · 2011-09-20T08:48:38.293

1

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.

edited Sep 20 '11 at 08:48

answered Sep 20 '11 at 08:39

ankit

860
7
11

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) – Martin York 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

score 0 · Answer 2 · answered Oct 13 '11 at 11:58

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;
}

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

2 Answers2