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.

Visualisation

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;
 }
}

• user33306: It looks to me like you're creating a new tree, but the challenge says In-Place.
• dfhwze: @tinstaafl If I take a look at the 'spoiler', they are doing the same. geeksforgeeks.org/…
• Mast: "The problem here is simpler as we don’t need to create circular DLL, but a simple DLL." That's in the spoiler. Do you want to write code that fits the spec of the original description or that fits the provided spoiler? There appear to be differences between the two.
• dfhwze: @Mast In case of discrepancy, the original spec. Whether the algorithm is circular or not doesn't matter, as long I don't change the class definitions and the outcome matches. I do notice now that the picture states 'In-Place' and I'm not adhering to that requirement.
• vnp: Because of recursion it still doesn't qualify as in-place. What they want to see is a variation on a Morris traversal theme.

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.

• dfhwze: My initial solution used circular linked list to avoid that first and last overhead, but this would work as well. I did not know about the Morris traversal theme, I learn every day.