Skip to main content

Tree Modification

DFS First​

Mirror Tree​

Easy·

Explanation

Solutions:
Visualize
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)

Exchange the Leaf Nodes​

Easy·

Explanation

Solutions:
Visualize
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

617. Merge Two Binary Trees​

Easy·

Explanation

Solutions:
Visualize
def mergeTrees(
self, root1: Optional[TreeNode], root2: Optional[TreeNode]
) -> Optional[TreeNode]:
def recursion(a, b):
if a and b:
node = TreeNode(a.val + b.val)
node.left = recursion(a.left, b.left)
node.right = recursion(a.right, b.right)
elif a:
node = TreeNode(a.val)
node.left = recursion(a.left, None)
node.right = recursion(a.right, None)
elif b:
node = TreeNode(b.val)
node.left = recursion(None, b.left)
node.right = recursion(None, b.right)
else:
return None
return node
 
return recursion(root1, root2)

Create a New Tree​

654. Maximum Binary Tree​

Medium·

Explanation

:::

Solutions:
Visualize
class Solution:
def find_max(self, nums, lo, hi) -> int:
max_element = nums[lo]
max_index = lo
for i in range(lo, hi):
if max_element < nums[i]:
max_index = i
max_element = nums[i]
return max_index
 
def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
def recursion(lo: int, hi: int):
if lo < hi:
maxi = self.find_max(nums, lo, hi)
node = TreeNode(val=nums[maxi])
node.left = recursion(lo, maxi)
node.right = recursion(maxi + 1, hi)
return node
 
return recursion(0, len(nums))

BFS First​

116. Populating Next Right Pointers in Each Node​

Medium·

Explanation

Solutions:
Visualize
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) if node.left else None
queue.append(node.right) if node.right else None
return root

117. Populating Next Right Pointers in Each Node II​

Medium·

TODO: Undertsnad the optimal approach with constact auxillary space

Explanation

Solutions:
Visualize
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