Convert Binary Tree to Doubly Linked List - Part 1

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.

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:

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

• $1 <= N$ (Number of nodes in the binary tree) $<= 10^5$
• Value in the data field can be any real number.

Approach 1: By Processing Subtrees

We need to convert the given binary tree to a doubly linked list in place, which means no extra space is needed. So the basic approach can be just manipulating the left and right pointer of the node to the next and previous pointers as in a doubly linked list. We can process the left subtree first and get the head of the doubly linked list, which is the leftmost node in the given binary tree. And by processing the right subtree we get the nodes that are to the right side of the root in the doubly linked list. Using the Inorder predecessor of the root in the left subtree which is considered to be the rightmost node in the left subtree and helps in attaching with the leftmost node of the right subtree and forming a DLL. And also using the Inorder successor of the root in the right subtree which is the leftmost node in the right subtree. The basic idea is to use recursion, to recursively convert each subtree into a doubly linked list.

Algorithm

The below algorithm clearly explains the approach for converting the given binary tree to a doubly linked list:

• Here, the idea is the left subtree is processed first and right subtree is processes next as in the Inorder traversal
• Check whether the left subtree exists, if it exists then follow the below three steps to convert the left subtree of the root to the doubly linked list:
  • Recursively call the left subtree to convert it into a doubly linked list.
  • For every call find the Inorder predecessor of the root in the left subtree which is considered to be the next element in the doubly linked list formed.
  • After finding the Inorder predecessor, name it as the previous node and now root is the next of the previous node (i.e next of the Inorder predecessor).
• Similarly for the right subtree, if the right subtree exists for the root. Follow the below steps if the right subtree of the root node exists:
  • Recursively call the right subtree to convert it into a doubly linked list.
  • For every recursive call on the right subtree, find the Inorder successor of the root in the right subtree.
  • After finding the Inorder successor make this node the next node of the root and root as the previous node of the Inorder successor.
• Return the leftmost node of the tree as the head node of the doubly linked list which is formed from the given binary tree.

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:

Python implementation for converting the given binary tree to the doubly linked list by processing subtrees:

Java implementation for converting the given binary tree to the doubly linked list by processing subtrees:

Output:

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.

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 to convert it into the doubly linked list.
• Therefore 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.

• Auxiliary stack space used during recursion.

Approach 2: Fixing Left and Right Pointers

A solution for converting the binary tree to a doubly linked list is using the inorder traversal and manipulating the pointers of the root's right and left pointer as the prev and next pointers as in the doubly linked list. This is can be achieved by simply performing the Inorder traversal on the given binary tree. And changing the left pointer using the previous pointer. Similarly, it changes the right pointer as the next pointer in the doubly linked list.

Algorithm

The below algorithm clearly explains the above-discussed approach for converting the given binary tree to the doubly linked list:

• We simply do an Inorder traversal on a tree and keep track of previously visited nodes in the traversal.
• For fixing the previous pointers in the DLL, follow the below steps:
  • While performing the Inorder traversal on the given binary tree, we keep track of the previously visited node and change the left pointer to the previous node.
• For fixing the next pointers in the DLL, follow the below steps:
• We use the left pointers of the node which are fixed as previous pointers of the DLL in the above step.
  • We start traversing from the rightmost node in the given input binary tree. The rightmost node is however considered to be the last node in a formed doubly linked list. However, left pointers of the node are manipulated to point to the previous node in the doubly linked list.
  • Now, we can linearly traverse the modified doubly linked list with the help of these previous pointers. The traversal goes from the rightmost node (last node) to the leftmost node (first node).
  • While traversing the modified doubly linked list, we keep track of the previously visited node and modify the right pointer pointing to the previous node of the DLL.

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:

Python implementation for converting the given binary tree to the doubly linked list by processing subtrees:

Java implementation for converting the given binary tree to the doubly linked list by processing subtrees:

Output:

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 to convert it into the doubly linked list. Because two traversals are performed on the tree.
• One traversal is performed to change the left pointers as the previous pointers and the other traversal for changing the right pointers as the next pointers in the doubly linked list.
• Therefore 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 3: Inorder Traversal (By Keeping Track Of DLL Head and Tail Pointers)

All the approaches discussed earlier deals with Inorder traversal and manipulating the left and right pointers of a node as the prev and next pointers to convert it into a doubly linked list. Similarly, this approach uses recursion to recursively convert the left subtree and right subtree separately and convert them into a doubly linked list. While traversing each node keep track of the head node and tail node of the DLL.

Algorithm

The below algorithm converts the given binary tree into a doubly linked list using recursion:

• Firstly, traverse the whole binary tree in an Inorder manner (left node of the root is processed first, the present node is inserted into the DLL with the help of the tail pointer, then the right node is processed).
• For every node which is visited, keep track of the head and tail pointers that are initialized for a doubly linked list.
• Insert every visited node to the end of the doubly linked list with the help of the tail pointer. By adding it to the tail pointer.
• Head pointer always has the first node of the doubly linked list.
• Return the head pointer at the end of all recursive calls i.e, when all the nodes in the tree are visited.

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:

Python implementation for converting the given binary tree to the doubly linked list by processing subtrees:

Java implementation for converting the given binary tree to the doubly linked list by processing subtrees:

Output:

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 and converted into head and tail pointers as in the doubly linked list.
• Therefore 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.

• Auxiliary stack space used during recursion for Inorder traversal performed on the given input binary tree.