Binary Tree to Doubly Linked List
Binary Tree to Doubly Linked List
This article will explain how to convert the given binary tree into a Doubly Linked List. The left and right pointers in tree nodes are to be used as previous and next pointers in the resultant doubly linked list. The order of nodes in the doubly linked list must be the same as inorder of the given binary tree. The first node of inorder traversal must be the head node of the doubly linked list.
Method:
In this method, we will traverse the binary tree and store its inorder representation in the arraylist. After this, we will make the doubly linked list by using that array list.
Algorithm of inorder traversal:
void inorder(Node temp)
{
if(temp == null)
return;
inorder(temp.left);
l.add(temp.data);
inorder(temp.right);
}
Algorithm of adding a node in the linked list:
void add(int data)
{
if(head == null)
{
head = new Node(data);
return;
}
else
{
Node temp = head;
while(temp.right != null)
{
temp = temp.right;
}
Node t = temp;
temp.right = new Node(data);
temp = temp.right;
temp.left = t;
}
}
Source code for in-place conversion of Binary Tree to Doubly Linked List using Java programming:
import java.util.*;
public class BinaryTree
{
static Node root, head;
// Arraylist for storing element of binary tree
ArrayList<Integer> l = new ArrayList<>();
// Structure of the node
static class Node
{
int data;
Node left = null;
Node right = null;
Node(int data)
{
this.data = data;
}
}
// Method for inorder traversal of the binary tree
void inorder(Node temp)
{
if(temp == null)
return;
inorder(temp.left);
l.add(temp.data);
inorder(temp.right);
}
// Method for adding a node in the doubly linked list
void add(int data)
{
if(head == null)
{
head = new Node(data);
return;
}
else
{
Node temp = head;
while(temp.right != null)
{
temp = temp.right;
}
Node t = temp;
temp.right = new Node(data);
temp = temp.right;
temp.left = t;
}
}
// Method to convert the binary tree to the doubly linked list
void binaryToDoubly()
{
inorder(root);
int i = 0;
while(i < l.size())
{
add(l.get(i));
i++;
}
}
// Method for print the elements of doubly linked list
void printList(Node temp)
{
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.right;
}
}
// Driver method of this program
public static void main(String args[])
{
BinaryTree ob = new BinaryTree ();
ob.root = new Node(9);
ob.root.left = new Node(13);
ob.root.right = new Node(16);
ob.root.left.left = new Node(23);
ob.root.left.right = new Node(35);
ob.root.right.left = new Node(39);
ob.binaryToDoubly();
System.out.println("Doubly Linked list:");
ob.printList(head);
}
}
Output:
Time Complexity: This method works on simple inorder traversal, so the time complexity of this method is O(n), where n is the number of nodes in a given binary tree.
Space Complexity: The space complexity of this method is O(n) because we use extra space for storing the elements of the binary tree.