Tree - Flatten Binary Tree to Linked List
All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.
Difficulty : Hard
DFS
Problem
Given the root
of a binary tree, flatten the tree into a “linked list”:
- The “linked list” should use the same
TreeNode
class where theright
child pointer points to the next node in the list and theleft
child pointer is alwaysnull
. - The “linked list” should be in the same order as a pre-order traversal of the binary tree.
Example 1:
1
2
Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]
Solution
The solution to this problem is not complicated, the code also is just few lines and simple to understand however you still may need to run this few time to fully grasp the idea.
Here is a diagram to start. We are going to use the TreeNode
as double linked list and simple set the left
pointer to None
to flatten it. As per the diagram, we are going to insert the left flatten subtree in between the root and its right sub tree.
The base case is simple, just return None
for leaf nodes. Remember is code is inside our dfs()
function.
1
2
if not root:
return None
We need to traverse all the way to the left leaf node as the problem statement indicates the ordering should be same as pre-order traversal. We will get the left most and right most node. Here is a diagram to understand this better.
- We are at the
root
node (pink)- The
root.left
is3
(Orange) - The
root.right
is4
(Green)
- The
- Traverse
- Find the
left_most
node (3
) [Red] - Find the
right_most
node (5
) [Blue]
- Find the
- Reassign
- Now we need to align them.
left_most.right
should point toright_most
root.right
should beroot.left
- Finally,
root.left
should beNone
- Now we need to align them.
1
2
leftmost_leaf = dfs(root.left)
rightmost_leaf = dfs(root.right)
If the root.left
is not None
then we need to switch its position in between current root
’s right
and the root
itself.
The
leftmost_leaf
should already be flatten unless it’s a single leaf node.
Point the end of the leftmost_leaf
to the right
of the current root
1
2
if root.left:
leftmost_leaf.right = root.right
Then, repoint root
’s right
to its left
The
root.left
won’t be always same asleftmost_leaf
1
root.right = root.left
Finally, set the root.left
to None
1
root.left = None
The last part is very important. Here we will decide what to return. If the rightmost_leaf
is not None
, mean the root
has a right
sub-tree. So we want to return the rightmost_leaf
of it. Lets review the same diagram here, when we are processing the node 2
, we want to return where the right of the node 1
can be connected and thats node 4
which is the rightmost_leaf
of node 2
.
1
2
if rightmost_leaf:
return rightmost_leaf
In case the rightmost_leaf
is None
, say we didn’t have node 4
in the tree. Then we want to return the leftmost_leaf
1
2
elif leftmost_leaf:
return leftmost_leaf
For the leaf nodes we are going to return the root
node itself.
1
2
else:
return root
Final Code
Here is the full code.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def flatten(root):
def dfs(root):
if not root:
return None
leftmost_leaf= dfs(root.left)
rightmost_leaf= dfs(root.right)
if root.left:
leftmost_leaf.right= root.right
root.right = root.left
root.left = None
# Converting all the if else to one line
return rightmost_leaf or leftmost_leaf or root
dfs(root)