Convert Binary tree to double linked list in inorder traversal

Problem

Given a Binary Tree (Bt), convert it to a Doubly Linked List(DLL). The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (left most node in BT) must be head node of the DLL.

Example

Input

 Output
4 -- 2 -- 5 -- 1 -- 3

Solution

Method 1 - Treating left pointer as back pointer and right pointer as forward pointer of DLL
1. If left subtree exists, process the left subtree
…..1.a) Recursively convert the left subtree to DLL.
…..1.b) Then find inorder predecessor of root in left subtree (inorder predecessor is rightmost node in left subtree).
…..1.c) Make inorder predecessor as previous of root and root as next of inorder predecessor.
2. If right subtree exists, process the right subtree (Below 3 steps are similar to left subtree).
…..2.a) Recursively convert the right subtree to DLL.
…..2.b) Then find inorder successor of root in right subtree (inorder successor is leftmost node in right subtree).
…..2.c) Make inorder successor as next of root and root as previous of inorder successor.
3. Find the leftmost node and return it (the leftmost node is always head of converted DLL).


Program in java:

// This is the core function to convert Tree to list. This function follows
//  steps 1 and 2 of the above algorithm 
Node BST2DLLInorder(Node root)
{
    // Base case
    if (root == null)
        return root
 
    // Convert the left subtree and link to root
    if (root.left != null)
    {
        // Convert the left subtree
        Node left = BST2DLLInorder(root.left);
 
        // Find inorder predecessor. After this loop, left
        // will point to the inorder predecessor
        for (; left.right!=null; left=left.right);
 
        // Make root as next of the predecessor
        left.right = root;
 
        // Make predecssor as previous of root
        root.left = left;
    }
 
    // Convert the right subtree and link to root
    if (root.right!=null)
    {
        // Convert the right subtree
        Node right = BST2DLLInorder(root.right);
 
        // Find inorder successor. After this loop, right
        // will point to the inorder successor
        for (; right.left!=null; right = right.left);
 
        // Make root as previous of successor
        right.left = root;
 
        // Make successor as next of root
        root.right = right;
    }
 
    return root;
}
 
// The main function that first calls BST2DLLInorder(), then follows step 3 
//  of the above algorithm
Node BST2DLL(Node root)
{
    // Base case
    if (root == null)
        return root;
 
    // Convert to DLL using BST2DLLInorder()
    root = BST2DLLInorder(root);
 
    // BST2DLLInorder() returns root node of the converted
    // DLL.  We need pointer to the leftmost node which is
    // head of the constructed DLL, so move to the leftmost node
    while (root.left != null)
        root = root.left;
 
    return (root);
}

Method 2 - Iterative Solution


In this post, another simple and efficient solution is discussed. The solution discussed here has two simple steps.
1) Fix Left Pointers: In this step, we change left pointers to point to previous nodes in DLL. The idea is simple, we do inorder traversal of tree. In inorder traversal, we keep track of previous visited node and change left pointer to the previous node. See fixPrevPtr() in below implementation.
2) Fix Right Pointers: The above is intuitive and simple. How to change right pointers to point to next node in DLL? The idea is to use left pointers fixed in step 1. We start from the rightmost node in Binary Tree (BT). The rightmost node is the last node in DLL. Since left pointers are changed to point to previous node in DLL, we can linearly traverse the complete DLL using these pointers. The traversal would be from last to first node. While traversing the DLL, we keep track of the previously visited node and change the right pointer to the previous node. See fixNextPtr() in below implementation.

// Standard Inorder traversal of tree
void inorder(Node root)
{
    if (root != null)
    {
        inorder(root.left);
        System.out.print(root.data+ " ");
        inorder(root.right);
    }
}
 
 static Node pre;
// Changes left pointers to work as previous pointers in converted DLL
// The function simply does inorder traversal of Binary Tree and updates
// left pointer using previously visited node
static void fixPrevPtr(Node root)
{
    static Node pre = null;
 
    if (root != null)
    {
        fixPrevPtr(root.left);
        root.left = pre;
        pre = root;
        fixPrevPtr(root.right);
    }
}
 
// Changes right pointers to work as next pointers in converted DLL
static Node fixNextPtr(Node root)
{
    Node prev = null;
 
    // Find the right most node in BT or last node in DLL
    while (root && root.right != null)
        root = root.right;
 
    // Start from the rightmost node, traverse back using left pointers.
    // While traversing, change right pointer of nodes.
    while (root && root.left != null)
    {
        prev = root;
        root = root.left;
        root.right = prev;
    }
 
    // The leftmost node is head of linked list, return it
    return (root);
}
 
// The main function that converts BST to DLL and returns head of DLL
Node BTToDLL(Node root)
{
    // Set the previous pointer
    fixPrevPtr(root);
 
    // Set the next pointer and return head of DLL
    return fixNextPtr(root);
}
 
// Traverses the DLL from left tor right
void printList(Node root)
{
    while (root != null)
    {
        printf("\t%d", root.data);
        root = root.right;
    }
}

References

• http://www.geeksforgeeks.org/in-place-convert-a-given-binary-tree-to-doubly-linked-list/
• http://www.geeksforgeeks.org/convert-a-given-binary-tree-to-doubly-linked-list-set-2/