Flatten Binary Tree To Linked List

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 non-linear data structure, so what we have to actually do here is to convert this non-linear 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:

![](https://blog.prepbytes.com/wp-content/uploads/2021/10/example-1-output.png)

Now, you might wonder how did we get the above-flattened 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.

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 (Brute-Force)

Now, the approach and algorithm for the brute-force 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.

Flatten Binary Tree To Linked List

Introduction

Problem Statement

Problem Statement Understanding

Approach and Algorithm (Brute-Force)

Code Implementation

Output

Approach (Pointer Method)

Algorithm (Pointer Method)

Dry Run

Code Implementation

Output

Leave a Reply Cancel reply

Difference between Big Oh, Big Omega, and Big Theta

Basics of Analysis of Algorithms

Types of Algorithm Analysis

Why Analysis of Algorithms is important?

What is meant by Algorithm Analysis?

Design and Analysis of Algorithms

Sign in to your account

Login via OTP

Login via OTP

Register with PrepBytes

Introduction

Problem Statement

Problem Statement Understanding

Approach and Algorithm (Brute-Force)

Code Implementation

Output

Approach (Pointer Method)

Algorithm (Pointer Method)

Dry Run

Code Implementation

Output

Leave a Reply Cancel reply