Problem Statement
Given a Binary Tree convert it into a Doubly Linked List (DLL) where the left and right pointers are modified to the previous and next pointers of the resultant Doubly linked list. The order of nodes in the doubly linked list should be the same as the order of the nodes in the Inorder traversal of the binary tree. Therefore the first node(head) of a doubly linked list will be the leftmost node of the binary tree since we are following Inorder traversal.
In Part 1 of this editorial we discussed three approaches, namely –
- Approach 1: By Processing Subtrees
- Approach 2: Fixing Left and Right Pointers
- Approach 3: Inorder Traversal (By Keeping Track Of DLL Head and Tail Pointers)
In this part we will discuss about recursive and iterative approaches.
Example
For a better understanding of the problem statement, let’s look at the below example:
Input:
Consider the input binary tree shown in the below image:
Output:
18 45 9 40 6 14 12
The doubly linked list formed is shown in the below image:
Example Explanation
We can observe that the order of the doubly linked list is the same as the Inorder traversal on the given binary tree. Therefore the nodes of the modified doubly linked list are printed as the output.
Input Format
During competitive programming, the input of the binary tree is given by indicating the value of the data field in each node by providing the root of the binary tree.
Output Format
The output includes printing the node’s values of the newly formed Doubly linked list. Print all the nodes in the doubly linked list.
Constraints
Approach 4: Using Recursion
This approach uses recursion to convert the given input binary tree into a doubly linked list. This solution is considered to be the simplest of the above approaches. This approach also uses Inorder traversal for manipulating the pointers of the binary tree to convert to a doubly linked list. In this approach, while performing an Inorder traversal on the given binary tree we need to keep track of previously visited nodes. In this approach we are just manipulating the right and left pointers to next and prev pointers of DLL unlike the above approach using tail pointer. We follow the Inorder traversal manner so that we can change the left and right pointers as the prev and next pointers to convert them into the doubly linked list.
Algorithm
Below algorithm clearly explains the above approach:
- Start traversing the given binary tree in an Inorder fashion, for every visited node follow the below steps:
- Keep track of the previously visited node in a variable, assume previous.
- And for every visited node, make its next pointing to the previous and previous of this node as the prev.
- In this Inorder fashion given input binary tree is converted into a doubly linked list.
Implementation
Below is the implementation of the approach which is discussed above for converting the given binary tree to the doubly linked list
C++ implementation for converting the given binary tree to the doubly linked list by processing subtrees:
// C++ program for converting the binary tree to a doubly linked list
#include <bits/stdc++.h>
using namespace std;
// Class of a node in the binary tree
class Node {
public:
int val;
Node* left;
Node* right;
};
// function which assigns the data to the newly formed node
Node* newNode(int data) {
Node* new_Node = new Node();
new_Node->val = data;
new_Node->left = NULL;
new_Node->right = NULL;
return (new_Node);
}
// A recursive function which converts the given binary tree to the doubly linked list
// head is the first node in the formed dll
// root is the root of the given binary tree
void BinaryTree_to_DLL(Node* root, Node** head) {
// Base case if the root is null
if (root == NULL)
return;
// Initialize previously visited "prev" node as NULL
static Node* prev = NULL;
// Recursively convert the left subtree of the root node
BinaryTree_to_DLL(root->left, head);
// if prev is null, that means the root is the head node of the dll
if (prev == NULL)
*head = root;
// else find the end of the DLL by traversing the right side
else {
root->left = prev;
prev->right = root;
}
// make the prev as the root node
prev = root;
// recursively call the right subtree of the root node
BinaryTree_to_DLL(root->right, head);
}
// Driver code
int main() {
// creating the tree by inserting nodes and corresponding node values into it
Node* root = newNode(15);
root->left = newNode(-45);
root->left->left = newNode(-10);
root->left->left->left = newNode(-20);
root->left->left->left->left = newNode(-40);
root->right = newNode(10);
root->right->right = newNode(40);
root->right->right->right = newNode(20);
root->right->right->right->right = newNode(45);
// Convert binary tree to DLL by calling the function
Node* head = NULL;
BinaryTree_to_DLL(root, &head);
// Print the converted doubly linked list
while (head != NULL) {
// print the data present in every node of the doubly linked list
cout << head->val << " ";
head = head->right;
}
return 0;
}
Python implementation for converting the given binary tree to the doubly linked list by processing subtrees:
# Python program to convert the binary tree to dll
# node of a binary tree
class Node:
# Constructor to create a new tree node
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# global variable used in the below recursive function
prev = None
# Main function which is used to convert the given binary tree to the DLL using recursion
def BinaryTree_to_DLL(root):
# Base case if the root is None
if root is None:
return root
# Recursively call the function for the left subtree of the subtree
head = BinaryTree_to_DLL(root.left);
# we need to use the global keyword for prev because we are going to change prev
global prev
# If prev is empty, then this is the first node of DLL
if prev is None :
# make the head of the dll
head = root
# else get the next node of the prev node
else:
root.left = prev
prev.right = root
# Update the value of the prev
prev = root;
# Recursively call the function for the right subtree of the subtree
BinaryTree_to_DLL(root.right);
# return the head of the converted DLL
return head
# driver code
if __name__ == '__main__':
# creatinf the binary tree by giving the values of nodes
root = Node(15)
root.left = Node(-45)
root.left.left = Node(-10)
root.left.left.left = Node(-20)
root.left.left.left.left = Node(-40)
root.right = Node(10)
root.right.right = Node(40)
root.right.right.right = Node(20)
root.right.right.right.right = Node(45)
# calling the function which converts the given binary tree to a doubly linked list
head = BinaryTree_to_DLL(root)
# printing the nodes in the doubly linked list
while head:
#printing the data in the node
print(head.val, end = " ")
head = head.right
Java implementation for converting the given binary tree to the doubly linked list by processing subtrees:
// Java program to convert the binary tree to a doubly linked list
// A binary tree node has data, left pointers, and right pointers
class Node {
int val;
Node left;
Node right;
// constructor for creating the new node in the tree
public Node(int val) {
this.val = val;
left = right = null;
}
}
class Solution {
// root the given binary tree
Node root;
// head is the first node in the formed dll
Node head;
// Initialize previously visited node as NULL
static Node prev = null;
// Print the converted doubly linked list
void print_DLL(Node head) {
while (head != null) {
// print the data present in every node of the doubly linked list
System.out.print(head.val + " ");
head = head.right;
}
}
// A recursive function which converts the given binary tree to the doubly linked list
// root is the root of the given binary tree
void binaryTree_to_dll(Node root) {
// Base case if the root is null
if (root == null)
return;
// Recursively convert the left subtree of the root node
binaryTree_to_dll(root.left);
// if prev is null, that means the root is the head node of the dll
if (prev == null){
head = root;
}
// else find the end of the DLL by traversing the right side
else {
root.left = prev;
prev.right = root;
}
// make the prev as the root node
prev = root;
// recursively call the right subtree of the root node
binaryTree_to_dll(root.right);
}
// Driver program to test above functions
public static void main(String[] args) {
// Let us create the tree as shown in the above diagram
Solution tree = new Solution();
tree.root = new Node(15);
tree.root.left = new Node(-45);
tree.root.right = new Node(10);
tree.root.left.left = new Node(-10);
tree.root.left.left.left = new Node(-20);
tree.root.left.left.left.left = new Node(-40);
tree.root.right.right = new Node(40);
tree.root.right.right.right = new Node(20);
tree.root.right.right.right.right = new Node(45);
// function called which converts binary tree to DLL
tree.binaryTree_to_dll(tree.root);
// Print the converted DLL
tree.print_DLL(tree.head);
}
}
Output:
-40 -20 -10 -45 15 10 40 20 45
Explanation: We can observe that the order of the doubly linked list is the same as the Inorder traversal on the given binary tree. The input binary tree is shown in the below image.
The nodes of the binary tree are converted to the nodes of the doubly linked list. These nodes’ values are printed as the output. The doubly linked list formed is shown in the below image:
Complexity Analysis
Time Complexity: O(N), where N is the number of nodes present in the given binary tree.
- Every node of the binary is traversed once during the Inorder traversal, therefore to convert the binary tree into a doubly linked list the overall time complexity of this approach is O(N).
Space Complexity: O(N), where N is the number of nodes present in the given binary tree.
- An auxiliary stack space of O(N) is used during recursion to keep track of the visited nodes during the Inorder traversal which is performed on the given tree.
Approach 5: Iterative Approach
All the above approaches deal with recursion, using an Inorder traversal we convert the binary tree to a doubly linked list. Inorder traversal can also be performed iteratively. Iterative Inorder traversal requires a stack data structure for keeping track of the visited nodes and their current level. Every node is inserted into the stack and a depth first traversal is performed to obtain the deepest leaf node first, then the right node, so in this way the tree is traversed in an Inorder fashion. Here the value of the level indicates whether the node’s left is processed or node is processed or node’s right is processed or not.
Algorithm
The below algorithm clearly explains the iterative Inorder traversal performed on the tree to convert it into a doubly linked list:
- Traversal is performed using the stack data structure of pair type. Firstly initialize the stack of type pair, because it has to store
<Node, int>and insert a pair(root node,0). Using a while loop on the stack, until the stack is empty, perform the below steps:- Pop the top element from the stack and extract its node and level separately.
- If the level is
3or the node’s value is Null, this is the base and we can move to the next top element in the stack. - If that’s not the case then push the [root, level+1] into the stack.
- Now, we need to check whether the extracted level has the value of
0, it indicates that we need to process the left side of the node. If the level is0whenever just push the node’s left and level=0 [node.left, 0] into the stack. - If the level is
1, then we need to process the node in it by converting it into a node of the doubly linked list. Check whether the prev is None, if the prev pointer is null and the flag is true, it indicates the present node is the first node in the doubly linked list and makes this the head of the doubly linked list. Change the value of the flag indicating the head of a doubly linked list is already discovered. - If the level is
2, it indicates that the present node’s left is processed, the node’s data is also processed and we need to process the right tree of the node, so we need to push [node.right, 0] into the stack.
- Whenever the level is
0, it means it that the node is processed for the first time. Where as level1indicates it’s the second time it is traversed, so we try to process it.
Implementation
Below is the implementation of the approach which is discussed above for converting the given binary tree to the doubly linked list:
C++ implementation for converting the given binary tree to the doubly linked list by processing subtrees:
// C++ program for converting the binary tree to a doubly linked list
#include <bits/stdc++.h>
using namespace std;
// Class of a node in the binary tree
class Node {
public:
int val;
Node* left;
Node* right;
};
// function which assigns the data to the newly formed node
Node* newNode(int data) {
Node* new_Node = new Node();
new_Node->val = data;
new_Node->left = NULL;
new_Node->right = NULL;
return (new_Node);
}
// iterative in order traversal on the given binary tree to convert it into dll
// root is the root of the given binary tree
Node *BinaryTree_to_DLL(Node *root) {
// stack is used for an iterative approach to keep track of nodes
stack<pair<Node*, int>> st;
// first push the root node with the level as 0
st.push({root, 0});
// flag here indicates whether we got the head of the doubly linked list or not
bool flag = true;
// head of the dll
Node* head = NULL;
//initialize the prev as NULL initially
Node* prev = NULL;
// traverse the tree while the stack is not empty
while(!st.empty()) {
// get the top element of the stack
auto n = st.top();
// get the node
Node* node = n.first;
// get the level of the top node
int level = n.second;
// pop the top element of the stack
st.pop();
// check whether the level is 3 and the node is null
if(level == 3 or node == NULL)
continue;
// else push the node in the stack and increment the level by 1
st.push({node, level+1});
// if the level is 0, then push the node's left to the stack
if(level == 0)
st.push({node->left, 0});
// if the level is 1
else if(level == 1) {
// check whether the prev is null
// if null is not null then it is not the first node of the dll
if(prev)
// make prev's next node as the node
prev->right = node;
// if null then it is the first node of the dll
node->left = prev;
prev = node;
//converting the given node to the node of the dll
if(flag) {
// make the node the head
head = node;
// flag is false because we got the head of the DLL, we don't need to update again
flag = false;
}
}
// check if the level is 2
// if the level is 2, push the right subtree into the stack
else if(level == 2) {
st.push({node->right, 0});
}
}
return head;
}
// Driver code
int main() {
// Let us create the tree shown in the above diagram
Node* root = newNode(20);
root->left = newNode(18);
root->left->left = newNode(17);
root->left->left->right = newNode(19);
root->left->left->right->left = newNode(22);
root->right = newNode(24);
root->right->left = newNode(-10);
root->right->left->right = newNode(40);
root->right->left->right->left = newNode(57);
// Convert binary tree to DLL
Node* head = NULL;
head= BinaryTree_to_DLL(root);
//BinaryTree_to_DLL(root);
// Print the converted doubly linked list
while (head != NULL) {
// print the data present in every node of the doubly linked list
cout << head->val << " ";
head = head->right;
}
return 0;
}
Python implementation for converting the given binary tree to the doubly linked list by processing subtrees:
# Python program to convert the binary tree to dll
# node of a binary tree
class Node:
# Constructor to create a new tree node
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# iterative in order traversal on the given binary tree to convert it into dll
# root is the root of the given binary tree
def BinaryTree_to_DLL(root):
# using a stack
st = []
# push the root node with the level as 0
st.append([root, 0])
# flag is used to keep track of the head of the DLL
flag = True
# the head of the DLL
head = None
# prev used in DLL
prev = None
# traverse the tree until the stack is empty
while len(st) > 0:
# pop the top element in the stack
s = st.pop()
# extract the node from the popped element
node = s[0]
# extract the value of the level of that particular node
level = s[1]
# check whether the level of the node is 3
# base case
if level == 3 or node == None:
continue
# else push the node with the incrementing the level by 1
st.append([node, level+1])
# if the level is 0, then push the node's left tree into the stack
if level == 0:
st.append([node.left, 0])
# if the level is 1, process the present node and convert its pointers to make it a dll
elif level == 1:
# if prev is None then it is not the first node of the dll
if prev != None:
prev.right = node
# make the node's left as the prev
node.left = prev
# update the value of prev
prev = node
# if the flag is true, then the node is the first node in the DLL
if flag:
# make the head of the DLL
head = node
flag = False
# if the level is 2, then push the right subtree of the root with the level0
elif level == 2:
st.append([node.right, 0])
return head
# driver code
if __name__ == '__main__':
# creatinf the binary tree by giving the values of nodes
root = Node(20);
root.left = Node(18);
root.left.left = Node(17);
root.left.left.right = Node(19);
root.left.left.right.left = Node(22);
root.right = Node(24);
root.right.left = Node(-10);
root.right.left.right = Node(40);
root.right.left.right.left = Node(57);
# calling the function which converts the given binary tree to a doubly linked list
head = BinaryTree_to_DLL(root)
# printing the nodes in the doubly linked list
while head:
#printing the data in the node
print(head.val, end = " ")
head = head.right
Java implementation for converting the given binary tree to the doubly linked list by processing subtrees:
// Java program to convert the binary tree to a doubly linked list
import java.util.*;
import javafx.util.Pair;
public class Solution{
// class which represents each node in the newly formed doubly linked list
static class Node {
int val;
Node left;
Node right;
// constructor for creating the new node in the tree
public Node(int val){
this.val = val;
}
}
// iterative in order traversal on the given binary tree to convert it into dll
// root is the root of the given binary tree
static Node binaryTree_to_dll(Node root) {
// stack is used for an iterative approach to keep track of nodes
Stack<Pair<Node,Integer>> st = new Stack<Pair<Node,Integer>>();
// first push the root node with the level as 0
st.push(new Pair<Node,Integer>(root, 0));
// flag here indicates whether we got the head of the doubly linked list or not
boolean flag = true;
// head of the dll
Node head = null;
//initialize the prev as NULL initially
Node prev = null;
// traverse the tree while the stack is not empty
while (!st.empty()) {
// get the top element of the stack
Pair<Node,Integer> t = st.peek();
// get the node
Node node = t.getKey();
// get the level of the top node
int level = t.getValue();
// pop the topmost node
st.pop();
// check whether the level is 3 and the node is null
if (level == 3 || node == null)
continue;
// else push the node in the stack and increment the level by 1
st.push(new Pair<Node,Integer>(node, level + 1));
// if the level is 0, then push the node's left to the stack
if (level == 0)
st.push(new Pair<Node,Integer>(node.left, 0));
// if the level is 1
else if (level == 1) {
// check whether the prev is null
// if null is not null then it is not the first node of the dll
if (prev != null)
prev.right = node;
// if null then it is the first node of the dll
node.left = prev;
prev = node;
// converting the given node to the node of the dll
if (flag) {
// make the node the head
head = node;
// flag is false because we got the head of the DLL, we don't need to update again
flag = false;
}
}
// check if the level is 2
// if level is 2, push the right subtree into the stack
else if (level == 2)
st.push(new Pair<Node,Integer>(node.right, 0));
}
return head;
}
// Driver program
public static void main(String[] args) {
// creating a binary tree by inserting nodes
Node root = new Node(20);
root.left = new Node(18);
root.left.left = new Node(17);
root.left.left.right = new Node(19);
root.left.left.right.left = new Node(22);
root.right = new Node(24);
root.right.left = new Node(-10);
root.right.left.right = new Node(40);
root.right.left.right.left = new Node(57);
// Convert the given bt to dll
Node head = binaryTree_to_dll(root);
// Print the converted doubly linked list
while (head != null) {
// print the data present in every node of the doubly linked list
System.out.print(head.val + " ");
head = head.right;
}
}
}
Output:
17 22 19 18 20 -10 57 40 24 Explanation:
We can observe that the order of the doubly linked list is the same as the Inorder traversal on the given binary tree. The input binary tree is shown in the below image.
The nodes of the binary tree are converted to the nodes of the doubly linked list. These nodes’ values are printed as the output. The doubly linked list formed is shown in the below image:
Complexity Analysis
Time Complexity: $O(N)$, where N is the number of nodes present in the given binary tree.
- Every node of the binary is traversed twice once to convert it into the doubly linked list, if the level of the node in the stack is
0, it is again pushed into the stack by incrementing the level, so every node is traversed twice. - Therefore the overall time complexity of this approach is $O(N+ N)$.
Space Complexity: $O(N)$, where N is the number of nodes present in the given binary tree.
- Extra space is needed during the iterative Inorder traversal on the given binary tree which uses stack data structure for keeping track of the nodes.
- The maximum number of elements in a stack is N, therefore the space complexity is $O(N)$.
Conclusion
- This article explained different approaches used to convert a given binary tree into a doubly linked list.
- All the approaches dealt with manipulating the left and right pointers of the tree into prev and next pointers as in the doubly linked list.
- Every approach uses Inorder traversal while converting into a doubly linked list.
- Time complexity of all the approaches is $O(N)$, and space complexity is $O(N)$. The difference between all the approaches is how the pointers are changed to make it a doubly linked list.
- Out of all these approaches Approach
4is considered to be simple and more efficient. - Approach
5uses the iterative Inorder traversal unlike other approaches to convert the binary tree into a doubly linked list.
