Last Updated on March 10, 2022 by Ria Pathak
Introduction
The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.
Problem Statement
Given a binary tree, flatten it into a linked list in place. After flattening, the left of each node should point to NULL, and the right should contain the next node in preorder.
Problem Statement Understanding
In this problem, we are given a binary tree, and we have to flatten it and represent it as a linked list.
Now, you all might be confused with the word flatten, this word simply means that as we know a tree data structure is a nonlinear data structure, so what we have to actually do here is to convert this nonlinear data structure to a linear data structure (linked list).
Now, let’s try to understand the problem with the help of examples.
Suppose we have a binary tree as:

Now, according to the problem statement, if we flatten the given binary tree, the flattened version of this binary tree will be:

Now, you might wonder how did we get the aboveflattened version.
 The answer is that if you have read the problem statement carefully, it tells us that we need to flatten the binary tree in such a way that the left child of every node is NULL, and the right child contains the next node in preorder, and here in the flattened version, we can clearly see that all the nodes have their left child as NULL and also right child of each node contains the next node in preorder.
![](https://blog.prepbytes.com/wpcontent/uploads/2021/10/example1output.png)
Now, taking another example to make it a bit more clear, If our binary tree is:

Now, try to draw on your own the flattened representation of the above binary tree.

If not able to draw, it’s okay; here we will understand step by step how a binary tree is flattened.
1) We can see that the extreme node to the left in the binary tree is 4, so we will make it as the right of its parent node 2. Also, make sure to preserve the preorder while shifting nodes.
2) Now we will shift all the left child nodes of the parent node 1 to its right following the constraint mentioned in the problem statement, i.e., the left of each node should point to NULL, and the right should contain the next node in preorder.
3) Finally, after the above steps, we will have our flattened binary tree in the form of a singly linked list.
Now, I think from the above examples, the problem statement is clear. Let’s see how we can approach it.
Before moving to the approach section, try to think about how you can approach this problem.
 If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.
Let’s move to the approach section.
Approach and Algorithm (BruteForce)
Now, the approach and algorithm for the bruteforce approach will be as follows:
 First, declare a stack named node_stk.
 Now we will iterate through the loop satisfying the condition that, either root node is not NULL or node_stk is not empty.
 Now, check if the right child of the current root node is not NULL:
 If yes then, push the right child in node_stk.
 After that shift, the left node of the current root node to its right, and point the left child to NULL.
 Now, if root>right == NULL and also node_stk is not empty:
 Then, it means that there was no left child of the current root node, so that’s why we have to make root>right point to the original root’s right node, which we pushed into the stack earlier.
 We will then pop the stack.
 We will then make root equal to root>right, and the above process will repeat until we flatten our binary tree completely.
Code Implementation
#include#include using namespace std; struct Node { int key; Node *left, *right; }; /* utility that allocates a new Node with the given key */ Node* newNode(int key) { Node* node = new Node; node>key = key; node>left = node>right = NULL; return (node); } // To find the inorder traversal void inorder(struct Node* root) { // base condition if (root == NULL) return; inorder(root>left); cout << root>key << " "; inorder(root>right); } // Function to convert binary tree into // linked list by altering the right node // and making left node point to NULL Node* solution(Node* A) { // Declare a stack stack st; Node* ans = A; // Iterate till the stack is not empty // and till root is Null while (A != NULL  st.size() != 0) { // Check for NULL if (A>right != NULL) { st.push(A>right); } // Make the Right Left and // left NULL A>right = A>left; A>left = NULL; // Check for NULL if (A>right == NULL && st.size() != 0) { A>right = st.top(); st.pop(); } // Iterate A = A>right; } return ans; } // Driver Code int main() { /* 1 / \ 2 5 / \ \ 3 4 6 */ // Build the tree Node* root = newNode(1); root>left = newNode(2); root>right = newNode(5); root>left>left = newNode(3); root>left>right = newNode(4); root>right>right = newNode(6); // Call the function to // flatten the tree root = solution(root); cout << "The Inorder traversal after " "flattening binary tree "; // call the function to print // inorder after flattening inorder(root); return 0; return 0; }
class Node: def __init__(self): self.key = 0 self.left = None self.right = None # Utility that allocates a new Node # with the given key def newNode(key): node = Node() node.key = key node.left = node.right = None return (node) # Function to convert binary tree into linked list def flatten(root): node_stk = [] ans = root # Iterate till the stack is not empty and till root is Null while (root or len(node_stk)): # Check for NULL if (root.right): node_stk.append(root.right) # Make the Right node Left and left node NULL root.right = root.left root.left = None # Check for NULL condition if (root.right == None and len(node_stk) != 0): root.right = node_stk[1] node_stk.pop() # Iterate to the right child root= root.right return ans # To find the inorder traversal def inorder(root): # Base condition if (root == None): return inorder(root.left) print(root.key, end = ' ') inorder(root.right) # Driver Code if __name__=='__main__': root = newNode(1) root.left = newNode(2) root.right = newNode(3) root.left.right = newNode(4) root.left.right.right = newNode(5) print("The Inorder traversal before flattening binary tree",end=" ") inorder(root) print() flatten(root) print("The Inorder traversal after " "flattening binary tree ", end = '') inorder(root)
class Node { int data; Node left, right; Node(int key) { data = key; left = right = null; } } class Flatten { Node root; public void flatten(Node node) { // Base case  return if root is NULL if (node == null) return; // Or if it is a leaf node if (node.left == null && node.right == null) return; // If root.left children exists then we have to make // it node.right (where node is root) if (node.left != null) { // Move left recursively flatten(node.left); // Store the node.right in Node named tempNode Node tempNode = node.right; node.right = node.left; node.left = null; // Find the position to insert the stored value Node curr = node.right; while (curr.right != null) curr = curr.right; // Insert the stored value curr.right = tempNode; } // Now call the same function for node.right flatten(node.right); } public void inOrder(Node node) { if (node == null) return; inOrder(node.left); System.out.print(node.data + " "); inOrder(node.right); } public static void main(String[] args) { Flatten tree=new Flatten(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(5); tree.root.left.left = new Node(3); tree.root.left.right = new Node(4); tree.root.right.right = new Node(6); System.out.println("The Inorder traversal after flattening binary tree "); tree.flatten(tree.root); tree.inOrder(tree.root); } }
Output
The Inorder traversal before flattening binary tree 2 4 5 1 3
The Inorder traversal after flattening binary tree 1 2 4 5 3
Time Complexity: O(n)
Space Complexity: O(n)
The above algorithm will work fine, but the main issue is that it takes O(n) extra space. Can we solve the above problem in O(1) extra space?
 Okay! If you can’t think of an approach, let me give you a hint from the previous solution.
 In the previous solution, we have used a stack to solve the problem; what if we use a pointer to temporarily store the right node and then keep putting it after left node, if it exists and this process would go on recursively till all the left child nodes are not NULL.
Still confused? Don’t worry, let’s get this recursive approach more clear by discussing it further.
Approach (Pointer Method)
Our approach will be:
 Since it will be a recursive approach, so we will need a base case that will terminate the function, and our base case will be:
 If root is NULL or if it is a leaf node, then return.
 Get a pointer that will point to the right child of the current parent node, and then replace the right child of the parent node with the left child node.
 Now, once the node is replaced, we will traverse to the rightmost leaf node of the tree and then will attach the last stored right node to the right of rightmost leaf node, because we have to preserve the order of nodes (preorder) which is given to us.
 And this process will be repeated till all the left child nodes are not NULL.
Now, to get a clear understanding of how this approach works, let’s have a look at its algorithm:
Algorithm (Pointer Method)
1) Base Case: if the root is NULL or the root is a leaf node, we will end the recursive function and return, else we will move on to step 2.
2) Now, we will check if the root has a left child.
 Yes, if the root has a left child, then store the right child of the root node in a pointer named right_child.
 After that, shift the left child of the root to the right child and make the left child NULL:
 root>right = root>left;
 root>left = NULL;
 And then, after shifting, we will traverse to the rightmost leaf node, and after reaching it, we will make its right pointer point to the node pointed by right_child.
3) Now, if there is no left child node, call the function recursively for the right child node and repeat the process.
Dry Run
Code Implementation
#include<stdio.h> #include<stdlib.h> struct Node { int key; struct Node *left; struct Node *right; }; /* utility that allocates a new Node with the given key */ struct Node* newNode(int key) { struct Node* node = malloc(sizeof(struct Node*)); node>key = key; node>left = node>right = NULL; return (node); } // Function to convert binary tree into // linked list by altering the right node // and making left node point to NULL void flatten(struct Node* root) { // base condition return if root is NULL // or if it is a leaf node if (root == NULL  root>left == NULL && root>right == NULL) { return; } // if root>left exists then we have // to make it root>right if (root>left != NULL) { // move left recursively flatten(root>left); // store the node root>right struct Node* tmpRight = root>right; root>right = root>left; root>left = NULL; // find the position to insert // the stored value struct Node* t = root>right; while (t>right != NULL) { t = t>right; } // insert the stored value t>right = tmpRight; } // now call the same function // for root>right flatten(root>right); } // To find the inorder traversal void inorder(struct Node* root) { // base condition if (root == NULL) return; inorder(root>left); printf("%d ",root>key); inorder(root>right); } /* Driver program to test above functions*/ int main() { /* 1 / \ 2 5 / \ \ 3 4 6 */ struct Node* root = newNode(1); root>left = newNode(2); root>right = newNode(5); root>left>left = newNode(3); root>left>right = newNode(4); root>right>right = newNode(6); flatten(root); printf( "The Inorder traversal after " "flattening binary tree "); inorder(root); return 0; }
#include <bits/stdc++.h> using namespace std; struct Node { int key; Node *left, *right; }; // utility that allocates a new Node with the given key Node* newNode(int key) { Node* node = new Node; node>key = key; node>left = node>right = NULL; return (node); } // Function to convert binary tree into linked list by // altering the right node and making left node point to // NULL void flatten(struct Node* root) { // base condition return if root is NULL or if it is a // leaf node if (root == NULL  root>left == NULL && root>right == NULL) return; // if root>left exists then we have to make it // root>right if (root>left != NULL) { // move left recursively flatten(root>left); // store the node root>right struct Node* tmpRight = root>right; root>right = root>left; root>left = NULL; // find the position to insert the stored value struct Node* t = root>right; while (t>right != NULL) t = t>right; // insert the stored value t>right = tmpRight; } // now call the same function for root>right flatten(root>right); } // To find the inorder traversal void inorder(struct Node* root) { // base condition if (root == NULL) return; inorder(root>left); cout << root>key << " "; inorder(root>right); } /* Driver program to test above functions*/ int main() { /* 1 / \ 2 5 / \ \ 3 4 6 */ Node* root = newNode(1); root>left = newNode(2); root>right = newNode(5); root>left>left = newNode(3); root>left>right = newNode(4); root>right>right = newNode(6); flatten(root); cout << "The Inorder traversal after flattening binary tree "; inorder(root); return 0; }
class Node { int data; Node left, right; Node(int key) { data = key; left = right = null; } } class Flatten { Node root; public void flatten(Node node) { if (node == null) return; if (node.left == null && node.right == null) return; if (node.left != null) { flatten(node.left); Node tempNode = node.right; node.right = node.left; node.left = null; Node curr = node.right; while (curr.right != null) { curr = curr.right; } curr.right = tempNode; } flatten(node.right); } public void inOrder(Node node) { if (node == null) return; inOrder(node.left); System.out.print(node.data + " "); inOrder(node.right); } public static void main(String[] args) { Flatten tree = new Flatten(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(5); tree.root.left.left = new Node(3); tree.root.left.right = new Node(4); tree.root.right.right = new Node(6); System.out.println("The Inorder traversal after " +"flattening binary tree "); tree.flatten(tree.root); tree.inOrder(tree.root); } }
class Node: def __init__(self): self.key = 0 self.left = None self.right = None # Utility that allocates a new Node # with the given key def newNode(key): node = Node() node.key = key node.left = node.right = None return (node) # Function to convert binary tree into linked list def flatten(root): # Base condition return if root is None # or if it is a leaf node if (root == None or root.left == None and root.right == None): return # If root.left exists then we have # to make it root.right if (root.left != None): # Move left recursively flatten(root.left) # Store the node root.right tmpRight = root.right root.right = root.left root.left = None # Find the position to insert # the stored value t = root.right while (t.right != None): t = t.right # Insert the stored value t.right = tmpRight # Now call the same function # for root.right flatten(root.right) # To find the inorder traversal def inorder(root): # Base condition if (root == None): return inorder(root.left) print(root.key, end = ' ') inorder(root.right) # Driver Code if __name__=='__main__': root = newNode(1) root.left = newNode(2) root.right = newNode(3) root.left.right = newNode(4) root.left.right.right = newNode(5) print("The Inorder traversal before flattening binary tree",end=" ") inorder(root) print() flatten(root) print("The Inorder traversal after " "flattening binary tree ", end = '') inorder(root)
Output
The Inorder traversal before flattening binary tree 2 4 5 1 3
The Inorder traversal after flattening binary tree 1 2 4 5 3
Time Complexity: The time complexity of this algorithm will be O(n), where n is the number of nodes in the binary tree
[forminator_quiz id=”5484″]
So, in this article, we have tried to explain the most efficient approach to flatten a binary tree to a linked list. This is an important question when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.