Flatten a binary tree into linked list

Given a binary tree, flatten it into linked list in-place. Usage of auxiliary data structure is not allowed. After flattening, left of each node should point to NULL and right should contain next node in preorder.

Examples: 

Input : 
          1
        /   \
       2     5
      / \     \
     3   4     6
Output :
    1
     \
      2
       \
        3
         \
          4
           \
            5
             \
              6
Input :
        1
       / \
      3   4
         /
        2
         \
          5
Output :
     1
      \
       3
        \
         4
          \
           2
            \ 
             5

Simple Approach: A simple solution is to use Level Order Traversal using Queue. In level order traversal, keep track of previous node. Make current node as right child of previous and left of previous node as NULL. This solution requires queue, but question asks to solve without additional data structure.

Efficient Without Additional Data Structure Recursively look for the node with no grandchildren and both left and right child in the left sub-tree. Then store node->right in temp and make node->right=node->left. Insert temp in first node NULL on right of node by node=node->right. Repeat until it is converted to linked list. Even though this approach does not require additional data structure , but still it takes space for Recursion stack.

For Example, 

Implementation:

The Inorder traversal after flattening binary tree 1 2 3 4 5 6 

Complexity Analysis:

• Time Complexity: O(n), traverse the whole tree
• Space Complexity: O(n), Extra space used for recursion call.

Another Approach:
We will use the intuition behind Morris’s traversal. In Morris Traversal we use the concept of a threaded binary tree.

• At a node(say cur) if there exists a left child, we will find the rightmost node in the left subtree(say prev).
• We will set prev’s right child to cur’s right child,
• We will then set cur’s right child to it’s left child.
• We will then move cur to the next node by assigning cur it to its right child
• We will stop the execution when cur points to NULL.

Implementation:

The Inorder traversal after flattening binary tree 1 2 3 4 5 6 

Time Complexity: O(N) Time complexity will be the same as that of a Morris’s traversal
Auxiliary Space: O(1)

Another Approach Using Stack:

In this solution, we start by initializing a prev variable to None. This variable will keep track of the previously flattened node as we recursively flatten the binary tree.

• We then define a recursive function flatten that takes in the root node of the binary tree. This function does not return anything, but instead modifies the tree in-place.
• The first thing we do in the flatten function is to check if the root node is None. If it is, we simply return.
• Next, we recursively flatten the right subtree of the root node by calling self.flatten(root.right). This will flatten the right subtree and set self.prev to the rightmost node in the right subtree.
• We then recursively flatten the left subtree of the root node by calling self.flatten(root.left). This will flatten the left subtree and update self.prev to the rightmost node in the flattened left subtree.
• Once we have flattened both the left and right subtrees, we update the root.right pointer to be the previously flattened node (self.prev). We also set the root.left pointer to None to remove the left child.
• Finally, we update self.prev to be the current node (root). This is important because it allows us to keep track of the previously flattened node as we continue to recursively flatten the tree.

This algorithm flattens the binary tree in pre-order traversal, so the resulting “linked list” will be in the same order as a pre-order traversal of the tree.

Implementation:

The Inorder traversal after flattening binary tree 1 2 3 4 5 6 

Time Complexity: O(N), The loop will execute for every node once.
Space Complexity: O(N), Auxiliary Stack Space is needed.