Tree Modification
DFS First
Mirror Tree
Explanation
- DFS (Recursive)
- DFS (Iterative)
- BFS
Analysis
- Python
def mirror(self, root):
def dfs(node):
if not node:
return
node.left, node.right = dfs(node.right), dfs(node.left)
return node
return dfs(root)
Analysis
- Python
def mirror(self, root):
stack = [root]
while stack:
node = stack.pop()
if node:
node.left, node.right = node.right, node.left
stack.append(node.right)
stack.append(node.left)
return root
Analysis
- Python
def mirror(self, root):
queue = collections.deque([root])
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node:
node.left, node.right = node.right, node.left
queue.append(node.left)
queue.append(node.right)
return root
Exchange the Leaf Nodes
Explanation
- DFS (Recursive)
- DFS (Iterative)
Analysis
- Python
def pairwiseSwap(self, root):
def dfs(node):
nonlocal swap
if not node:
return
if is_leaf(node):
if swap:
node.data, swap.data = swap.data, node.data
swap = None
else:
swap = node
dfs(node.left)
dfs(node.right)
is_leaf = lambda node: not node.left and not node.right
swap = None
dfs(root)
return root
Analysis
- Python
def pairwiseSwap(self, root):
stack = [root]
swap = None
is_leaf = lambda node: not node.left and not node.right
while stack:
node = stack.pop()
if node:
if is_leaf(node):
if swap:
node.data, swap.data = swap.data, node.data
swap = None
else:
swap = node
stack.append(node.right)
stack.append(node.left)
return root
BFS First
116. Populating Next Right Pointers in Each Node
Explanation
- BFS
- DFS (Recursive)
- DFS (Iterative)
- ⭐ Using Previously Established Next Pointers
Analysis
- Python
def connect(self, root: "Optional[Node]") -> "Optional[Node]":
queue = collections.deque([root])
while queue:
length = len(queue)
for i in range(length):
node = queue.popleft()
if node:
node.next = queue[0] if queue and (i != length - 1) else None
queue.append(node.left)
queue.append(node.right)
return root
Analysis
- Python
def connect(self, root: "Optional[Node]") -> "Optional[Node]":
def dfs(node, n):
if not node:
return
node.next = n
dfs(node.left, node.right)
dfs(node.right, n.left if n else None)
return node
return dfs(root, None)
Analysis
- Python
def connect(self, root: "Optional[Node]") -> "Optional[Node]":
stack = [(root, None)]
while stack:
node, n = stack.pop()
if node:
node.next = n
stack.append((node.right, n.left if n else None))
stack.append((node.left, node.right))
return root
Explanation
The key insight is to use the next pointers from the current level to establish connections for the next level. We process level by level:
- Connection 1: Connect left child to right child of same parent:
node.left.next = node.right - Connection 2: Connect right child to left child of next node:
node.right.next = node.next.left
Since this is a perfect binary tree, we can always rely on the leftmost node of each level being the left child of the previous level's leftmost node.
Analysis
- Python
def connect(self, root: "Optional[Node]") -> "Optional[Node]":
leftmost = root
while leftmost and leftmost.left:
head = leftmost
while head:
head.left.next = head.right
if head.next:
head.right.next = head.next.left
head = head.next
leftmost = leftmost.left
return root
117. Populating Next Right Pointers in Each Node II
TODO: Undertsnad the optimal approach with constact auxillary space
Explanation
- BFS
Analysis
- Python
def connect(self, root: "Node") -> "Node":
queue = collections.deque([root])
while queue:
length = len(queue)
for i in range(length):
node = queue.popleft()
if node:
node.next = queue[0] if queue and (i != length - 1) else None
queue.append(node.left) if node.left else None
queue.append(node.right) if node.right else None
return root