Converting an ordered binary tree to a doubly circular link list

Question

I have a ordered binary tree:
              4
              |
          |-------|
          2       5
          |
      |-------|
      1       3

The leaves point to null. I have to create a doubly link list which should look like

1<->2<->3<->4<->5

(Obviously 5 should point to 1)

The node class is as follows:

class Node {
    Node left;
    Node right;
    int value;

    public Node(int value)
    {
        this.value = value;
        left = null;
        right = null;
    }
}

As you can see the doubly link list is ordered (sorted) as well.

Question: I have to create the linked list form the tree without using any extra pointers. The left pointer of the tree should be the previous pointer of the list and the right pointer of the tree should be the next pointer of the list.

What I thought off: Since the tree is an ordered tree, the inorder traversal would give me a sorted list. But while doing the inorder traversal I am not able to see, where and how to move the pointers to form a doubly linked list.

P.S I checked some variations of this question but none of them gave me any clues.

Answer 1

It sounds like you need a method that accepts a Node reference to the root of the tree and returns a Node reference to the head of a circular list, where no new Node objects are created. I would approach this recursively, starting with the simple tree:

   2
   |
|-----|
1     3

You don't say whether the tree is guaranteed to be full, so we need to allow for 1 and/or 3 being null. The following method should work for this simple tree:

Node simpleTreeToList(Node root) {
    if (root == null) {
        return null;
    }
    Node left = root.left;
    Node right = root.right;
    Node head;
    if (left == null) {
        head = root;
    } else {
        head = left;
        left.right = root;
        // root.left is already correct
    }
    if (right == null) {
        head.left = root;
        root.right = head;
    } else {
        head.left = right;
        right.right = head;
        right.left = root;
    }
    return head;
}

Once it is clear how this works, it isn't too hard to generalize it to a recursive method that works for any tree. It is a very similar method:

Node treeToList(Node root) {
    if (root == null) {
        return null;
    }
    Node leftTree = treeToList(root.left);
    Node rightTree = treeToList(root.right);
    Node head;
    if (leftTree == null) {
        head = root;
    } else {
        head = leftTree;
        leftTree.left.right = root;
        root.left = leftTree.left;
    }
    if (rightTree == null) {
        head.left = root;
        root.right = head;
    } else {
        head.left = rightTree.left;
        rightTree.left.right = head;
        rightTree.left = root;
        root.right = rightTree;
    }
    return head;
}

If I got all the link assignments covered correctly, this should be all you need.

Answer 2

Do an in-order traversal of the list, adding each list item to the doubly linked list as you encounter it. When done, add an explicit link between the first and last items.

Update 3/6/2012: Since you must reuse the Node objects you already have, after you put the node objects into the the list, you can then iterate over the list and reset the left and right pointers of the Node objects to point to their siblings. Once that is done, you can get rid of the list and simply return the first node object.

Answer 3

This should also work:

NodeLL first = null;
NodeLL last = null;
private void convertToLL(NodeBST root) {
    if (root == null) {
        return;
    }
    NodeLL newNode = new NodeLL(root.data);
    convertToLL(root.left);   
    final NodeLL l = last;
    last = newNode;
    if (l == null)
        first = newNode;
    else {
        l.next = newNode;
        last.prev = l;
    }
    convertToLL(root.right);
}

Answer 4

Let your recursion return the left and right end of formed list. Then you link your current node to the last of the left list, and first of the right list. Basic case it, when there is no left or right element, which is the node it self for both. Once all is done, you can link the first and last of the final result. Below is the java code.

static void convertToSortedList(TreeNode T){
    TreeNode[] r = convertToSortedListHelper(T);
    r[1].next = r[0];
    r[0].prev= r[1];

}
static TreeNode[] convertToSortedListHelper(TreeNode T){        
    TreeNode[] ret = new TreeNode[2];
    if (T == null) return ret;
    if (T.left == null && T.right == null){ 
        ret[0] = T;
        ret[1] = T;
        return ret;
    }       
    TreeNode[] left = TreeNode.convertToSortedListHelper(T.left);
    TreeNode[] right = TreeNode.convertToSortedListHelper(T.right);

    if (left[1] != null) left[1].next = T;
    T.prev = left[1];

    T.next = right[0];
    if (right[0] != null) right[0].prev = T;

    ret[0] = left[0]==null? T:left[0];
    ret[1] = right[1]==null? T:right[1];

    return ret;
}

Answer 5

Add the following method to your Node class

public Node toLinked() {
    Node leftmost = this, rightmost = this;
    if (right != null) {
        right = right.toLinked();
        rightmost = right.left;
        right.left = this;
    }
    if (left != null) {
        leftmost = left.toLinked();
        left = leftmost.left;
        left.right = this;
    }
    leftmost.left = rightmost;
    rightmost.right = leftmost;
    return leftmost;
}

EDIT By maintaining the invariant that the list returned by toLinked() has the proper form, you can easily get the left- and rightmost nodes in the sublist returned by the recursive call on the subtrees

Answer 6

/*  input: root of BST. Output: first node of a doubly linked sorted circular list. **Constraints**: do it in-place.     */

public static Node transform(Node root){

        if(root == null){
            return null;
        }

        if(root.isLeaf()){

            root.setRight(root);
            root.setLeft(root);
            return root;

        }

        Node firstLeft = transform(root.getLeft());
        Node firstRight = transform(root.getRight());
        Node lastLeft = firstLeft == null ? null : firstLeft.getLeft();
        Node lastRight=  firstRight == null ? null : firstRight.getLeft();

        if(firstLeft != null){

           lastLeft.setRight(root);
           root.setLeft(lastLeft);

           if(lastRight == null){

               firstLeft.setLeft(root);

           }
           else{

               firstLeft.setLeft(lastRight);
               root.setRight(firstRight);
           }
        }

        if(firstRight != null){

           root.setRight(firstRight);
           firstRight.setLeft(root);       

           if(lastLeft == null){

               root.setLeft(lastRight);
               lastRight.setLeft(root);
               firstLeft = root;

           }
           else{

               root.setLeft(lastLeft);
               lastRight.setRight(firstLeft);
           }
        }

        return firstLeft;
}