Tree Modification

DFS First

226. Invert Binary Tree

Easy·

Mirror Tree

E

226Invert Binary Tree

Invert a binary tree by swapping the left and right subtrees of every node, so the result is the mirror image of the input.

3 Approaches

DFS (Recursive)

O(n) timeO(h) aux

DFS (Iterative)

O(2n) timeO(h) aux

BFS

O(n) timeO(w) aux

FIG. INVERT BINARY TREE● INTERACTIVE

visualization loads as you reach it

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution:

def invertTree(self, root: TreeNode | None) -> TreeNode | None:

def rec(node):

if not node:

return

left = rec(node.left) if node.left else None

right = rec(node.right) if node.right else None

node.left, node.right = right, left

return node

 

return rec(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 Approaches

DFS (Recursive)

O(n) timeO(h) aux

DFS (Iterative)

O(n) timeO(h) aux

FIG. EXCHANGE THE LEAF NODES● INTERACTIVE

visualization loads as you reach it

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 Approaches

DFS (Recursive)

O(m + n) timeO(h) aux

DFS (Iterative)

O(m + n) timeO(h) aux

FIG. MERGE TWO BINARY TREES● INTERACTIVE

visualization loads as you reach it

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)

---

2415. Reverse Odd Levels of Binary Tree

Medium·

2415Reverse Odd Levels of Binary Tree

The tree is perfect, so reversing a level means swapping values between nodes that are mirror images of each other across the tree's vertical axis. Walk mirror pairs instead of whole levels and each swap is a single exchange.

3 Approaches

Mirror Pair Recursion

O(n) timeO(h) aux

Explicit Stack with Visited Flag

O(n) timeO(h) aux

Level Order with Reversed Child Values

O(4n) timeO(3w) aux

FIG. REVERSE ODD LEVELS OF BINARY TREE● INTERACTIVE

visualization loads as you reach it

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution:

def reverseOddLevels(self, root: TreeNode | None) -> TreeNode | None:

def rec(left, right, level):

if not left or not right:

return

if level % 2 == 0:

left.val, right.val = right.val, left.val

rec(left.left, right.right, level + 1)

rec(left.right, right.left, level + 1)

 

rec(root.left, root.right, 0) if root else None

return root

---

814. Binary Tree Pruning

Medium·

814Binary Tree Pruning

Remove every subtree that contains no 1. Post-order is what makes this work: a child is pruned before its parent reports up, so by the time a parent looks at a child it is already the collapsed version of itself.

rec returns a pair (zero_flag, total) - whether the subtree is all zeros, and how many nodes it still has after pruning. A child is cut when zero == total, which holds in exactly two cases: the child is absent (0 == 0), or it survived as a single all-zero node (1 == 1). Because both children are detached before the parent returns left_total + right_total + 1, any all-zero subtree keeps shrinking to one node on the way up, so it is always caught. The root gets the same test via rec(root) == (1, 1).

DFS (Recursive)

O(n) timeO(h) aux

FIG. BINARY TREE PRUNING● INTERACTIVE

visualization loads as you reach it

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution:

def pruneTree(self, root: TreeNode | None) -> TreeNode | None:

def rec(node):

if not node:

return 0, 0

left_zero, left_total = rec(node.left)

right_zero, right_total = rec(node.right)

if left_zero == left_total:

node.left = None

left_zero = left_total = 0

if right_zero == right_total:

node.right = None

right_zero = right_total = 0

return left_zero + right_zero + node.val == 0, left_total + right_total + 1

 

if rec(root) == (1, 1):

return None

return root

---

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.

DFS (Recursive)

O(n^2) timeO(n) aux

FIG. MAXIMUM BINARY TREE● INTERACTIVE

visualization loads as you reach it

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 Approaches

BFS

O(n) timeO(w) aux

DFS (Recursive)

O(n) timeO(h) aux

DFS (Iterative)

O(n) timeO(h) aux

⭐ Using Previously Established Next Pointers

O(n) timeO(1) aux

FIG. POPULATING NEXT RIGHT POINTERS BFS● INTERACTIVE

visualization loads as you reach it

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.

BFS

O(n) timeO(w) aux

FIG. POPULATING NEXT RIGHT POINTERS II● INTERACTIVE

visualization loads as you reach it

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

---

623. Add One Row to Tree

Medium·

623Add One Row to Tree

Insert a whole row of val nodes at depth. Every node that was at depth keeps its subtree - it just gets re-parented, a left child staying a left child and a right child staying a right child. So the real work happens at level depth - 1, and depth == 1 is its own case because there is no parent level to work from.

3 Approaches

Level Order Graft

O(2n) timeO(2w) aux

Recursive Graft

O(2k) timeO(depth) aux

Iterative Stack Graft

O(2k) timeO(depth) aux

FIG. ADD ONE ROW TO TREE● INTERACTIVE

visualization loads as you reach it

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution:

def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:

if depth == 1:

return TreeNode(val, left=root)

queue = collections.deque([root])

level = 1

while queue:

for _ in range(len(queue)):

node = queue.popleft()

if node:

queue.append(node.left)

queue.append(node.right)

if level == depth - 1:

node.left = TreeNode(val, left=node.left)

node.right = TreeNode(val, right=node.right)

level += 1

return root

---