package recursion3;

class TreeNode {
    public int value;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int value) {
        this.value = value;
    }

}

class ListNode {
    public int key;
    public ListNode next;
    public ListNode prev;

    public ListNode(int key) {
        this.key = key;
        this.next = null;
        this.prev = null;
    }
}

public class BtreeToDDL {
    TreeNode prev = null;
    TreeNode head = null;

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(10);
        TreeNode node2 = new TreeNode(5);
        TreeNode node3 = new TreeNode(15);
        TreeNode node4 = new TreeNode(2);
        TreeNode node5 = new TreeNode(7);
        TreeNode node6 = new TreeNode(12);
        TreeNode node7 = new TreeNode(20);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        BtreeToDDL bd = new BtreeToDDL();
        bd.BinaryTree2DoubleLinkedList(node1);

        while (bd.head != null) {
            System.out.println("** " + bd.head.value);
            bd.head = bd.head.right;
        }
        while (bd.prev != null) {
            System.out.println(" -- " + bd.prev.value);
            bd.prev = bd.prev.left;
        }
    }

    void BinaryTree2DoubleLinkedList(TreeNode root) {
        if (root == null)
            return; // Base case
        // Initialize previously visited node as NULL. This is static so that
        // the same value is accessible in all recursive calls
        BinaryTree2DoubleLinkedList(root.left);
        if (prev == null) {
            head = root;// unique case at the beginning
        } else {
            root.left = prev; // point to left
            prev.right = root;// point to right
        }
        prev = root;
        BinaryTree2DoubleLinkedList(root.right);
    }

}