Given a binary tree, convert it to double linked list

     10

/ \

5 15

/ / \

2 7 12 20

2<->5<->7<->10<->12<->15<->20

key point:

inorder traverse + right as next, left as prev

we must know which node is previous node

know which node is the new head

public class BinaryTreeSerilization {
    TreeNode prev = null;



    public TreeNode BinaryTree2DoubleLinkedList(TreeNode root) {

        // left as prev pointer

        // right as next pointer in double linked list



        if (root == null) {

            return root ;

        }

        //TreeNode head = null;

        TreeNode dummyHead = new TreeNode(0);

        convert2DLL(root,dummyHead);

        TreeNode newHead = dummyHead.right;

        newHead.left = null;

        return newHead;

    }



    private void convert2DLL(TreeNode root,TreeNode head) {

        //base case

        if (root == null) {
            return;
        }

        convert2DLL(root.left,head);

        if (prev == null) {
                head.right = root;
                root.left =  head;
        } else {
                root.left = prev;
                prev.right = root;
        }
        prev = root;

        //System.out.format("%d, %d,",head.key,prev.key);
        convert2DLL(root.right,head);

    }
   }