Tree Modification

DFS First

Mirror Tree

Easy3 solutionsexplanationanalysis1 playground

---

Mirror Tree

Explanation

Solutions:

Interactive Visualization

Analysis

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

Easy2 solutionsexplanationanalysis1 playground

---

Exchange the Leaf Nodes

Explanation

Solutions:

Interactive Visualization

Analysis

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

---

BFS First

116. Populating Next Right Pointers in Each Node

Medium4 solutionsexplanationanalysis1 playground

---

116. Populating Next Right Pointers in Each Node

Explanation

Solutions:

Analysis

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

Medium1 solutionexplanationanalysis1 playground

---

117. Populating Next Right Pointers in Each Node II

TODO: Undertsnad the optimal approach with constact auxillary space

Explanation

Solutions:

Interactive Visualization

Analysis

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

---