Convert a given Binary Tree to Doubly Linked List

Question:

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.(Taken from GeeksForGeeks)

The idea behind its solution is quite simple and straight.

1.  If left subtree exists, process the left subtree
1. Recursively convert the left subtree to DLL.
2. Then find inorder predecessor of root in left subtree (inorder predecessor is rightmost node in left subtree).
3. 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).
1. Recursively convert the right subtree to DLL.
2. Then find inorder successor of root in right subtree (inorder successor is leftmost node in right subtree).
3. 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).

 Solution :

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 29/1/14
 * Time: 5:43 PM
 */
public class BTreeToList {

    private static TreeNode btreeToListUtil(TreeNode root){

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

        if(root.getLeftNode() != null){

            TreeNode leftTreeNode = btreeToListUtil(root.getLeftNode());

            while(leftTreeNode.getRightNode() != null){
                leftTreeNode = leftTreeNode.getRightNode();
            }

            leftTreeNode.setRightNode(root);
            root.setLeftNode(leftTreeNode);

        }


        if(root.getRightNode() != null){

            TreeNode rightTreeNode = btreeToListUtil(root.getRightNode());

            while(rightTreeNode.getLeftNode() != null){
                rightTreeNode = rightTreeNode.getLeftNode();
            }

            rightTreeNode.setLeftNode(root);
            root.setRightNode(rightTreeNode);
        }

        return root;

    }

    public static TreeNode btreeToList(TreeNode root){
         TreeNode head = btreeToListUtil(root);
        while(head.getLeftNode() != null){
            head = head.getLeftNode();
        }

        return head;
    }

    public static void printLL(TreeNode root){

        while(root != null){
            System.out.println("Data : " + root.getData());
            root = root.getRightNode();
        }


    }



    public static void main(String args[]){

        TreeNode root = new TreeNode(10);

        TreeNode l = new TreeNode(12);
        TreeNode r = new TreeNode(15);

        TreeNode ll = new TreeNode(25);
        TreeNode lr = new TreeNode(30);

        TreeNode rl = new TreeNode(36);

        root.setLeftNode(l);
        root.setRightNode(r);

        l.setLeftNode(ll);
        l.setRightNode(lr);

        r.setLeftNode(rl);

        printLL(btreeToList(root));

    }

}

Output :

Data : 25
Data : 12
Data : 30
Data : 10
Data : 36
Data : 15