This approach involves a recursive pre-order traversal of the tree. The idea is to recursively flatten the left and right subtrees, then append the flattened left subtree between the root and the flattened right subtree.
The steps are as follows:
This leverage the pre-order traversal principle: Root → Left → Right.
Time Complexity: O(n) where n is the number of nodes in the tree since each node is visited once.
Space Complexity: O(n) due to the recursive call stack on an unbalanced tree.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def flatten(self, root: TreeNode) -> None:
9 if not root:
10 return
11
12 left = root.left
13 right = root.right
14
15 root.left = None
16 self.flatten(left)
17 self.flatten(right)
18
19 root.right = left
20 curr = root
21 while curr.right:
22 curr = curr.right
23 curr.right = rightIn Python, this solution follows the recursive approach to rearrange the given binary tree. The 'left' and 'right' are stored initially to rearrange nodes correctly after flattening both subtrees.
This approach simplifies the recursive method by using a stack to maintain state information. By using controlled use of stack structures, we can modify the tree iteratively.
The algorithm progresses with these steps:
This achieves similar logic as recursion but without directly using the call stack by using our custom stack for maintaining traversal state.
Time Complexity: O(n) because every node is processed once.
Space Complexity: O(n), matching the worst-case stack usage when all nodes are in a single path.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def flatten(self, root: TreeNode) -> None:
9 if not root:
10 return
11
12 stack = [root]
13
14 while stack:
15 current = stack.pop()
16
17 if current.right:
18 stack.append(current.right)
19
20 if current.left:
21 stack.append(current.left)
22
23 if stack:
24 current.right = stack[-1]
25
26 current.left = NoneThe Python iteration utilizes a stack to simulate recursion for flattening the tree by pre-order alignment. It extracts nodes from the stack in `right-first` fashion during each traversal iteration.