Convert a Binary Tree to Doubly Linked List

Question

Challenge

Link on geeksforgeeks: Binary Tree to DLL

Given a Binary Tree (BT), convert it to a Doubly Linked List(DLL) In-Place. 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.

Your Task:

You don't have to take input. Complete the function bToDLL() that takes node and head as parameter. The driver code prints the DLL both ways.

The following code is given. Class Node may not be changed. Method bToDLL must be implemented, but its signature may not be changed.

class Node
{
    Node left, right;
    int data;

    Node(int d)
    {
        data = d;
        left = right = null;
    }

}

// This function should convert a given Binary tree to Doubly Linked List
class GfG
{
    Node head;
    Node bToDLL(Node root)
    {
        // TODO .. convert tree and store the result as head
    }
}

---

Solution

As pointed out in the comments, a solution is required to be in-place. This is what I came up with. Any type of feedback is invited.

class GfG
{
    Node head;
    Node bToDLL(Node root)
    {
        head = first(reduce(root));
        return head;
    }

    void append(final Node source, final Node node) {
        source.right = node;
        node.left = source;
    }

    Node reduce(final Node node) {
        if (node == null) return node;
        Node prev = reduce(node.left);
        Node next = reduce(node.right);
        if (prev != null) append(last(prev), node);
        if (next != null) append(node, first(next));
        return node;
    }

    Node first(Node node) {
        while (node.left != null) node = node.left;
        return node;
    }

    Node last(Node node) {
        while (node.right != null) node = node.right;
        return node;
    }
}

Answer 1

Algorithm: because of the recursion, it still doesn't qualify as in-place. Consider a variation on a Morris traversal theme.

---

The calls to first() and last() are detrimental to the performance. Meanwhile, the callee already computed them. Consider returning a (fake) node pointing the beginning and the end of the flattened subtree, along the lines

    left = flatten(root.left);
    right = flatten(root.right);

    left.right.next = root;
    root.left = left.right;

    right.left.left = root;
    root.right = right.left;

    return Node(left.left, right.right);

There is only \$O(h)\$ Nodes to exist at any given moment, so the space complexity is not compromised.