Extract Leaves of a Binary Tree in a Doubly Linked List

Given a Binary Tree, the task is to extract all leaves of it in a Doubly Linked List (DLL). Note that the DLL needs to be created in-place. Assume that the node structure of DLL and Binary Tree is the same, only the meaning of left and right pointers are different. In DLL, left means previous pointer and right means next pointer. Head of DLL should point to the leftmost leaf and then in inorder traversal and so on.

Input: The first line of input contains the number of test cases T. For each test case, there will be only a single line of input which is a string representing the tree as described below:

1. The values in the string are in the order of level order traversal of the tree where, numbers denote node values, and a character “N” denotes NULL child.

2. For example:

For the above tree, the string will be: 1 2 3 N N 4 6 N 5 N N 7 N

Output: For each testcase, there will be three lines. First-line contains inorder traversal of the tree(after extracting leaves). The second and third line contains the nodes of DLL, first in order of inorder traversal of tree and next in reverse order.

User Task: The task is to complete the function convertToDLL() which takes the root of the given binary tree as input and returns the head of the doubly link list. This function should extract the leaf nodes into a doubly link list and modify the original binary tree by excluding the leaf nodes.

Expected Time Complexity: O(N). Expected Auxiliary Space: O(H). Note: H is the height of the tree and this space is used implicitly for recursion stack.

Constraints: 1 <= T <= 100 1 <= N <= 104 1 <= Data on Node <= 104

Example: Input:

2 1 2 3 1 2 3 4

Output:

1 2 3 3 2 2 1 4 3 3 4

Explanation: Testcase 2: After extracting leaves, 3 and 4 from the tree, the inorder traversal of the remaining binary tree produces 2, 1 and we have doubly linked list as 4 <-> 3.

class Tree {
    // Dummy head & tail for DLL
    Node head, tail;

    public Node convertToDLL(Node root) {
        head = new Node(0);
        tail = new Node(0);
        head.right = tail;
        tail.left = head;
        helper(root);
        Node ans = head.right;
        // Removing dummy nodes from DLL
        ans.left = null;
        tail.left.right = null;
        return ans;
    }

    public Node helper(Node root) {
        if (root == null)
            return null;
        if (root.left == null && root.right == null) {
            // Inserting new node at the end
            Node previous = tail.left;
            previous.right = root;
            root.left = previous;
            root.right = tail;
            tail.left = root;
            // Because we want to remove leaf nodes from tree aswell
            return null;
        }
        root.left = helper(root.left);
        root.right = helper(root.right);
        return root;
    }
}