CareerCup

We will use the left as prev and right as next pointer.

// converts and returns head and tail of doubly linked list
Pair <DLL *> InplaceConvert(Tree * root) {
    Pair result; // Default initialize head and tail to NULL
    if (!root) return result;
  
    if (root->left) {
        Pair leftResult = InplaceConvert(root->left);
        result.head = leftResult.head;
        leftResult.tail.right = root;
    }
    if (root->right) {
        Pair rightResult = InplaceConvert(root->right);
        root->right = rightResult.head;
        result.tail = right.Resullt.tail;
    }
    return result;
}

How about in-order traversal through the tree and while doing so link the nodes.

pseudo code

int main(int argc, char *argv[])
{
	constructDLList(root, null);	
	return 0;
}



void constructDLList(Tree* root, Node* prev){
	
	if (!root) return;

	constructDLList(root.left, prev);
	root.left = prev;
	if(prev != null)
		prev.right = root;
	prev = root;
	constructDLList(root.right,prev);
}

If the binary tree is immutable, then

static class Node {
        Node left;
        Node right;
        Object value;

        Node(Object value) {
            this.value = value;
        }
    }

    static class ListNode<ValueType> {
        ListNode<ValueType> prev;
        ListNode<ValueType> next;
        ValueType value;

        ListNode(ValueType value) {
            this.value = value;
        }
    }

 public static ListNode<Node> doubleLinkedList(final Node root) {
        ListNode<Node> headNode = null;

        if (root.right != null) {
            headNode = doubleLinkedList(root.right);
        }

        if (headNode == null) {
            headNode = new ListNode<Node>(root);
        } else {
            headNode.prev = new ListNode<Node>(root);
            headNode.prev.next = headNode;
            headNode = headNode.prev;
        }

        if (root.left != null) {
            ListNode<Node> tmpListNode = doubleLinkedList(root.left);

            ListNode<Node> newHead = tmpListNode;

            while (tmpListNode.next != null) {
                tmpListNode = tmpListNode.next;
            }

            tmpListNode.next = headNode;
            headNode = newHead;
        }

        return headNode;
    }

If binary tree is mutable, then call topDoubleLinkedList(rootNode):

static class Node {
        Node left;
        Node right;
        Object value;

        Node(Object value) {
            this.value = value;
        }
    }

public static Node topDoubleLinkedList(Node root)
	{
		Node headNode = doubleLinkedList(root);
		
		while(headNode.left!=null)
		{
			headNode=headNode.left;
		}
		
		return headNode;
	}
	
    public static Node doubleLinkedList(Node root) {
        if (root.right != null) {
            Node newNode = doubleLinkedList(root.right);

            Node tmpNode = newNode;

            while (tmpNode.left != null) {
                tmpNode = tmpNode.left;
            }

            tmpNode.left = root;
            root.right = tmpNode;
        }

        if (root.left != null) {
            Node newNode = doubleLinkedList(root.left);

            Node tmpNode = newNode;

            while (tmpNode.right != null) {
                tmpNode = tmpNode.right;
            }

            tmpNode.right = root;
            root.left = tmpNode;
            root = tmpNode;
        }

        return root;
    }

public class BinarySearchTreeDoublyLinkedListTransformer {

	// @formatter:off
	private static final Node TREE = 
		// Level 0
		node( 5,
			// Level 1
			node( 3,
				// Level 2
				node( 2,
					// Level 3
					node( 1 ),
					null
				),
				node(
					4					
				)			
			),
			node( 7,
				node(
					6
				),
				null				
			)			
		);
		// @formatter:on

	public static void main(String[] args) {
		// Test on tree
		testTree(TREE);
	}

	public static void testTree(Node root) {
		Node head = transform(root);

		Node node = head;
		do {
			System.out.print(node + " -> ");
			node = node.right;
		} while (node != head);
	}

	public static Node transform(Node node) {
		// Notes:
		// - let "->" and "<-" mean "points to"
		// - node.left is logically node.previous
		// - node.right is logically node.next
		// - leftHead.left is logically leftTail
		// - rightHead.left is logically rightTail
		// - leftHead.left.right is logically leftTail.next
		// - rightHead.left.right is logically rightTail.next

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

		Node leftHead = transform(node.left);
		Node rightHead = transform(node.right);
		Node head;

		if (leftHead == null) {
			head = node;
		} else {
			head = leftHead;

			// leftTail.next -> node
			leftHead.left.right = node;

			// leftTail <- node.previous
			node.left = leftHead.left;
		}

		if (rightHead == null) {
			// node <- head.previous
			head.left = node;

			// node.next -> head
			node.right = head;
		} else {
			// rightTail.next <- head.previous
			head.left = rightHead.left.right;

			// rightTail.next -> head
			rightHead.left.right = head;

			// node <- rightHead.previous
			rightHead.left = node;
		}

		return head;
	}

	private static Node node(Object value) {
		return node(value, null, null);
	}

	private static Node node(Object value, Node left, Node right) {
		Node node = new Node();
		node.value = value;
		node.left = left;
		node.right = right;

		return node;
	}

	private static class Node {
		Node left;
		Node right;
		Object value;

		@Override
		public String toString() {
			return value.toString();
		}

	}

}

We can use a queue and make the linkedlist level by level.

Node binaryTreeToDoubleLinkedList(Node root){

if(root == null) return null;
Queue<Node> q = new Queue<Node>();
LNode head = new LNode(root.value);
LNode tail = head;

q.enqueue(root);

while(!q.isEmpty()){
Node t = q.dequeue();

if(t.left!=null){
LNode l = new LNode(t.left.value);
tail.next = l;
l.pre = tail;
tail =l;
q.enqueue(t.left);
}
if(t.right!=null){
LNode l = new LNode(t.right.value);
tail.next = l;
l.pre = tail;
tail =l;
q.enqueue(t.right);
}
}

return


}