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)

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

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.

  • 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?
    – Giorgio
    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)     
    var l, r, head, tail;
    if ( node.left !== undefined)
        l = walktree(node.left );
        node.prev = l.tail;
        l.tail.next = node;
        head = l.head;
        head = node;
    if ( node.right !== undefined)
        r = walktree(node.right );
        node.next = r.head;
        r.head.prev = node;
        tail = r.tail;
        tail = node;
    return { head: head, tail: tail};

// test harness
var llnode = llist.head;
while ( llnode !== undefined)
    document.writeln( llnode.data );
    llnode = llnode.next;

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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