Flatten Binary Tree To Linked List

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);
}

// Print the final inorder traversal of the tree
void inorderTraversal(struct Node* root)
{
    if (root == NULL)
    return;
    inorderTraversal(root->left);
    cout << root->key << " ";
    inorderTraversal(root->right);
}

// Function to convert binary tree into a linked list
Node* flattenTree(Node* root)
{

    // Declare a stack
    stack node_stk;
    Node* ans = root;

    // Iterate till the stack is not empty and till root is Null
    while (root != NULL || node_stk.size() != 0) {

        // Check for NULL
        if (root->right != NULL) {
            node_stk.push(root->right);
        }

        // Make the Right node  Left and left  node NULL
        root->right = root->left;
        root->left = NULL;

        // Check for NULL condition
        if (root->right == NULL && node_stk.size() != 0) {
            root->right = node_stk.top();
            node_stk.pop();
        }

        // Iterate to the right child
        root= root->right;
    }
    return ans;
}



/* Driver program to test above functions*/
int main()
{
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->right = newNode(4);
    root->left->right->right = newNode(5);

    cout << "The Inorder traversal before "
            "flattening binary tree ";
    inorderTraversal(root);

    flattenTree(root);
    cout<

						 

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

/* C++ Program to flatten a given Binary
Tree into linked list */
#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);
}

// Function to convert binary tree into linked list
void flattenTree(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 root recursively
        flattenTree(root->left);
    
        // store the node root->right
        struct Node* right_child= root->right;
        root->right = root->left;
        root->left = NULL;

        // find the position to insert the stored value 
        struct Node* right_ptr = root->right;
        while (right_ptr->right != NULL) {
            right_ptr = right_ptr->right;
        }

        // insert the stored value
        right_ptr->right = right_child;
    }

    // now call the same function for root->right
    flattenTree(root->right);
}

// To find the inorder traversal
void inorderTraversal(struct Node* root)
{
    // base condition
    if (root == NULL)
        return;
    inorderTraversal(root->left);
    cout << root->key << " ";
    inorderTraversal(root->right);
}

/* Driver program to test above functions*/
int main()
{
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->right = newNode(4);
    root->left->right->right = newNode(5);

    cout << "The Inorder traversal before "
            "flattening binary tree ";
    inorderTraversal(root);

    flattenTree(root);
    cout<

						 

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

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.

Previous post C Program For Merge Sort For Linked Lists
Next post Flatten a multi-level linked list (Depth wise)

Leave a Reply

Your email address will not be published. Required fields are marked *