This question was asked in a recent coding interview.
Q : Given a binary tree, write a program to convert it to a doubly linked list. The nodes in the doubly linked list are arranged in a sequence formed by a zig-zag level order traversal
My approach
i could always do the zig-zag level order traversal of the tree and store it in an array an then make a double linked list. but the question demands for a in-place solution. can anyone help in explaining the recursive approach should be used?
A reverse inorder traversal without global variables - c# implementation. While calling, null will be passed to the right parameter initially. The final return value is the head of the doubly linked list
public static Node ToDLL(Node node, Node right)
{
if (node == null)
return null;
var rnd = ToDLL(node.Right, right);
if (rnd != null)
{
node.Right = rnd;
rnd.Left = node;
}
else
{
node.Right = right;
if (right!= null)
right.Left= node;
}
return ToDLL(node.Left, node) ?? node;
}
Here is Java code. Complexity is O(N). I also add some test cases for this problem.
public class BinaryToDoubleLinkedList {
static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
static class Pair {
Node head;
Node tail;
public Pair(Node head, Node tail) {
this.head = head;
this.tail = tail;
}
}
static Pair convertToDoubleLinkedList(Node root) {
return convert(root);
}
static Pair convert(Node root) {
if (root == null) return new Pair(null, null);
Node head, last;
Pair left = convert(root.left);
if (left.tail != null) {
left.tail.right = root;
root.left = left.tail;
head = left.head;
} else {
head = root;
}
Pair right = convert(root.right);
if (right.head != null) {
right.head.left = root;
root.right = right.head;
last = right.tail;
} else {
last = root;
}
return new Pair(head, last);
}
static void Print(Node root, boolean fromLeft) {
System.out.println("---------");
if (fromLeft) {
while (root != null) {
System.out.print(root.value + ",");
root = root.right;
}
} else {
while (root != null) {
System.out.print(root.value + ",");
root = root.left;
}
}
System.out.println();
}
public static void main(String[] args) {
test1();
test2();
test3();
}
// test 1: normal test case
public static void test1() {
Node root = new Node(10, null, null);
root.left = new Node(12, null, null);
root.right = new Node(15, null, null);
root.left.left = new Node(25, null, null);
root.left.right = new Node(30, null, null);
root.right.left = new Node(36, null, null);
Pair res = convertToDoubleLinkedList(root);
Print(res.head, true);
Print(res.tail, false);
}
// test 2: binary tree as linked list
public static void test2() {
Node root = new Node(1, null, null);
root.left = new Node(2, null, null);
root.left.left = new Node(3, null, null);
root.left.left.left = new Node(4, null, null);
Pair res = convertToDoubleLinkedList(root);
Print(res.head, true);
Print(res.tail, false);
}
// test 3: null and single
public static void test3() {
Node root = new Node(1, null, null);
Pair res = convertToDoubleLinkedList(root);
Print(res.head, true);
Print(res.tail, false);
res = convertToDoubleLinkedList(null);
Print(res.head, true);
Print(res.tail, false);
}
}
Finding the in-order predecessor and pointing the left and right to the predecessor of the current root will do the job for you. The time complexity to run the below code is O(N) and will take the auxiliary space O(H), where H = Height of the Tree, being implicitly used for the recursion stack. The below code is written using Python 3.
def convertToDLL(root):
# Base check
if root is None:
return root
# Converting left sub-tree to root
if root.left:
# Convert the left subtree
left = convertToDLL(root.left)
while left.right:
left = left.right
left.right = root
root.left = left
# Converting right sub-tree to root
if root.right:
# Convert the right subtree
right = convertToDLL(root.right)
while right.left:
right = right.left
right.left = root
root.right = right
return root
def bToDLL(root):
if root is None:
return root
# Convert to DLL
root = convertToDLL(root)
while root.left:
root = root.left
return root
def display(head):
# Display
if head is None:
return
while head:
print(head.data, end=" ")
head = head.right
Steps:
Inorder traversal of the tree
During the node processing step, keep track of head and tail and keep incrementing the tail
Reconnect head and tail at the end
def binarysearchtreeToLL(root):
def dfsInorder(node):
nonlocal head, tail
if not node:
return None
dfsInorder(node.left)
if tail:
tail.right = node
node.left = tail
else:
head = node
tail = node
dfsInorder(node.right)
if not root:
return None
head, tail = None, None
dfsInorder(root)
head.left = tail
tail.right = head
return head
Time Complexity: O(n) Space Complexity: O(n) in worst case where n recursion stack calls are made.