Mirror a Binary Tree in DSA Go - Execution Trace

Concept Flow - Mirror a Binary Tree

Start at root node

↓

Swap left and right children

↓

Mirror left subtree recursively

↓

Mirror right subtree recursively

↓

Return mirrored subtree

↓

Done

Start at the root, swap its left and right children, then recursively do the same for each subtree until all nodes are processed.

Execution Sample

DSA Go

func mirror(node *Node) *Node {
  if node == nil {
    return nil
  }
  node.Left, node.Right = mirror(node.Right), mirror(node.Left)
  return node
}

This function swaps left and right children of each node recursively to create the mirror image of the binary tree.

Execution Table

Step	Operation	Node Visited	Pointer Changes	Tree State (Visual)
1	Start at root	1	None	1 / \ 2 3 / \ \ 4 5 6
2	Swap children of node 1	1	Left=3, Right=2	1 / \ 3 2 \ / \ 6 4 5
3	Mirror left subtree of node 1 (node 3)	3	None yet	1 / \ 3 2 \ / \ 6 4 5
4	Swap children of node 3	3	Left=nil, Right=6	1 / \ 3 2 \ / \ 6 4 5
5	Mirror left subtree of node 3 (nil)	nil	None	1 / \ 3 2 \ / \ 6 4 5
6	Mirror right subtree of node 3 (node 6)	6	None yet	1 / \ 3 2 \ / \ 6 4 5
7	Swap children of node 6	6	Left=nil, Right=nil	1 / \ 3 2 \ / \ 6 4 5
8	Mirror left subtree of node 6 (nil)	nil	None	1 / \ 3 2 \ / \ 6 4 5
9	Mirror right subtree of node 6 (nil)	nil	None	1 / \ 3 2 \ / \ 6 4 5
10	Mirror right subtree of node 1 (node 2)	2	None yet	1 / \ 3 2 \ / \ 6 4 5
11	Swap children of node 2	2	Left=5, Right=4	1 / \ 3 2 \ / \ 6 5 4
12	Mirror left subtree of node 2 (node 5)	5	None yet	1 / \ 3 2 \ / \ 6 5 4
13	Swap children of node 5	5	Left=nil, Right=nil	1 / \ 3 2 \ / \ 6 5 4
14	Mirror left subtree of node 5 (nil)	nil	None	1 / \ 3 2 \ / \ 6 5 4
15	Mirror right subtree of node 5 (nil)	nil	None	1 / \ 3 2 \ / \ 6 5 4
16	Mirror right subtree of node 2 (node 4)	4	None yet	1 / \ 3 2 \ / \ 6 5 4
17	Swap children of node 4	4	Left=nil, Right=nil	1 / \ 3 2 \ / \ 6 5 4
18	Mirror left subtree of node 4 (nil)	nil	None	1 / \ 3 2 \ / \ 6 5 4
19	Mirror right subtree of node 4 (nil)	nil	None	1 / \ 3 2 \ / \ 6 5 4
20	Return mirrored tree	1	None	1 / \ 3 2 \ / \ 6 5 4

💡 All nodes visited and children swapped, recursion ends.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 11	Final
node	root=1	root=1	node=3	node=2	root=1
node.Left	2	3	nil	5	3
node.Right	3	2	6	4	2
Tree State	Original	Root swapped children	Left subtree mirrored	Right subtree mirrored	Fully mirrored

Key Moments - 3 Insights

Why do we swap children before recursive calls?

Swapping children first (see Step 2) ensures that when recursion happens, the left subtree is actually the original right subtree and vice versa, so the mirror is correctly formed.

What happens when a node is nil?

When node is nil (see Steps 5, 8, 9), the function returns immediately without changes, stopping recursion on that path.

Why do we assign node.Left, node.Right = mirror(node.Right), mirror(node.Left)?

This simultaneously swaps the children and recursively mirrors subtrees, as shown in Step 2 and throughout the recursion.

Visual Quiz - 3 Questions

Look at the execution table, what is the left child of node 1 after Step 2?

A Node 4

B Node 2

C Node 3

D Node 5

💡 Hint

Check the 'Pointer Changes' and 'Tree State' columns at Step 2.

At which step does the function first visit node 6?

A Step 6

B Step 4

C Step 10

D Step 12

💡 Hint

Look for 'Node Visited' column in the execution table.

If the tree had no right child at root, what would happen at Step 2?

A Left child becomes nil, right child stays the same

B Left and right children swap, right becomes nil

C No swap happens

D Function returns nil immediately

💡 Hint

Refer to how swapping works in Step 2 with existing children.

Concept Snapshot

Mirror a Binary Tree:
- Swap left and right children of each node
- Recursively apply to subtrees
- Base case: nil node returns nil
- Result is a tree flipped around its root
- Code: node.Left, node.Right = mirror(node.Right), mirror(node.Left)

Full Transcript

To mirror a binary tree, start at the root node. Swap its left and right children. Then recursively do the same for the left and right subtrees. If a node is nil, return nil immediately. This process flips the tree around its root, creating a mirror image. The code swaps children first, then calls mirror recursively on the swapped children. This ensures the entire tree is mirrored correctly.