Flatten Binary Tree to Linked List

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
63 upvotes
Asked in companies
DunzoQuikrMakeMyTrip

Problem statement

You are given a binary tree consisting of 'n' nodes.


Convert the given binary tree into a linked list where the linked list nodes follow the same order as the pre-order traversal of the given binary tree.


Use the right pointer of the binary tree as the “next” pointer for the linked list and set the left pointer to NULL.


Use these nodes only. Do not create extra nodes.


Example : 
Input: Let the binary be as shown in the figure:

Example Tree

Output: Linked List: 15 -> 40 -> 62 -> 10 -> 20 -> NULL

Explanation: As shown in the figure, the right child of every node points to the next node, while the left node points to null.

Also, the nodes are in the same order as the pre-order traversal of the binary tree.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains elements in the level order form for the first binary tree. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.


Input format explanation: 
The level order input for the tree depicted in the below image would be

alt text

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Explanation :
Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level, and so on.
The input ends when all nodes at the last level are null (-1).


Output format: 
The nodes of the linked list, each separated by a single space, are printed.


Note : 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Sample input 1:
15 40 62 -1 -1 10 20 -1 -1 -1 -1


Sample output 1:
15 40 62 10 20


Explanation for Sample Input 1:
The binary tree and the corresponding linked list are given in the following figure:

Example Tree

As shown in the figure, the right child of every node points to the next node, while the left node points to null.
Also, the nodes are in the same order as the pre-order traversal of the binary tree.


Sample Input 2 :
1 2 3 -1 -1 4 -1 5 -1 -1 -1


Sample Output 2 :
1 2 3 4 5


Explanation of sample input 2 :
The binary tree and the corresponding linked list are given in the following figure:

Testcase 2 Tree

As shown in the figure, the right child of every node points to the next node, while the left node points to null.
Also, the nodes are in the same order as the pre-order traversal of the binary tree, that is [1, 2, 3, 4, 5].


Expected time complexity :
The expected time complexity is O(n).


Constraints:
1 <= 'n' <= 10 ^ 5
1 <= 'data' in any node <= 10^5

Time limit: 1 sec
Hint

Can you solve this problem using stack?

Approaches (3)
Using Stack
  • A simple approach to solve this problem is by using a stack.
  • The idea is to implement the pre-order traversal of the tree using a stack.

 

Below is the detailed algorithm:

 

  1. We start by creating an empty stack and taking the root node as the current node.
  2. During the exploration of the current node, we check:
    • If the current node has the right child, then we push it to the stack.
    • If the current node has a left child, then make the left child the new right child of the node and set the left pointer to NULL.
      • This is done because the left child is the pre-order successor of the current node hence it must appear just after the current node in the linked list.
      • And since we are using the right pointer of the tree as the next pointer for the linked list. Hence, we set the right pointer to the left child.
    • Otherwise, if the stack is not empty, we have found the pre-order predecessor of the node present at the top of the stack.
      • So, pop the top node from the stack and make it the right child of the current node.
  3. Now, set the right child of the node as the current node.
  4. Repeat the above steps until the current node becomes NULL or the stack becomes empty.
Time Complexity

O(n), where ‘n’ is the number of nodes in the tree.

 

We are visiting every node of the tree once. Hence, the overall time complexity is O(n).

Space Complexity

O(n), where ‘n’ is the length of the list.

 

O(n) extra space is required for the stack. Hence, overall space complexity is O(n).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Flatten Binary Tree to Linked List
Full screen
Console