Tree Modification

DFS First

Mirror Tree

Easy·

Mirror Tree

Mirror a binary tree by swapping the left and right subtrees of every node. The mirror operation transforms the tree so that the left child becomes the right child and vice versa.

3 Approachesclick to switch

1

DFS (Recursive)

O(n)

O(h)

2

DFS (Iterative)

O(n)

O(h)

3

BFS

O(n)

O(w)

FIG. MIRROR TREE● INTERACTIVE

visualization loads as you reach it

Time

O(n)

• dfs visits each node once to swap its children.

Space

O(h)

• The recursion stack depth equals tree height h.

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·

Exchange the Leaf Nodes

Pairwise swap all leaf nodes of a binary tree. If there are odd number of leaf nodes, the last leaf node remains unchanged.

2 Approachesclick to switch

1

DFS (Recursive)

O(n)

O(h)

2

DFS (Iterative)

O(n)

O(h)

FIG. EXCHANGE THE LEAF NODES● INTERACTIVE

visualization loads as you reach it

Time

O(n)

• dfs visits each of the n nodes exactly once, doing constant work per call.

Space

O(h)

• The recursion call stack grows one frame per level, up to the tree height h.

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·

617Merge Two Binary Trees

Overlay the two trees: where both have a node, the merged node holds the sum of their values; where only one has a node, that subtree is carried over unchanged. A parallel DFS walks both trees in lockstep, building the merged tree node by node.

2 Approachesclick to switch

1

DFS (Recursive)

O(m + n)

O(h)

2

DFS (Iterative)

O(m + n)

O(h)

FIG. MERGE TWO BINARY TREES● INTERACTIVE

visualization loads as you reach it

Time

O(m + n)

• recursion only stops (return None) once both a and b are None; whenever either tree still has a node, it keeps descending and copying that side over. So every node of both root1 (size m) and root2 (size n) is visited exactly once - m + n.

Space

O(h)

• The recursion keeps descending into whichever tree is deeper even after the other side runs out, so the call stack grows to the height h of the taller of the two trees.

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·

654Maximum Binary Tree

Build the tree recursively: the largest value in the current range becomes the root, the elements to its left form the left subtree, and the elements to its right form the right subtree. Repeating this on each half constructs the maximum binary tree.

This is also called a Cartesian Tree. One interesting property is that if we do an in-order traversal, we get back the array used to create it.

1

DFS (Recursive)

O(n^2)

O(n)

FIG. MAXIMUM BINARY TREE● INTERACTIVE

visualization loads as you reach it

Time

O(n^2)

• find_max scans its [lo, hi) range, and recursion calls it once per node - in the worst case (sorted input) each call only shrinks the range by one, giving n + (n - 1) + ... + 1, O(n^2).

Space

O(n)

• The recursion stack reaches depth n in the worst case, when the input is already sorted and the tree is fully skewed.

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·

116Populating Next Right Pointers in Each Node

Given a perfect binary tree, populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

FOLLOW UP: You may only use constant extra space.

Source: Leetcode

4 Approachesclick to switch

1

BFS

O(n)

O(n)

2

DFS (Recursive)

O(n)

O(h)

3

DFS (Iterative)

O(n)

O(h)

4

⭐ Using Previously Established Next Pointers

O(n)

O(1)

FIG. POPULATING NEXT RIGHT POINTERS BFS● INTERACTIVE

visualization loads as you reach it

Time

O(n)

• Each of the n nodes is popped from queue and processed exactly once.

Space

O(n)

• queue holds at most n/2 nodes at once - the widest (last) level of a perfect binary tree.

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·

117Populating Next Right Pointers in Each Node II

TODO: Undertsnad the optimal approach with constact auxillary space

Given a binary tree, populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

FOLLOW UP: You may only use constant extra space.

1

BFS

O(n)

O(n)

FIG. POPULATING NEXT RIGHT POINTERS II● INTERACTIVE

visualization loads as you reach it

Time

O(n)

• n is the number of nodes in the tree.
• Each node is popped from queue and processed exactly once, with O(1) work per node.

Space

O(n)

• queue holds every node of the widest level at once, which can grow up to O(n) nodes in the worst case (e.g. a perfect tree's last level holds close to n/2 nodes).

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

---