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.

Practice

1. What does it mean to mirror a binary tree?

easy

A. Swap the left and right children of every node in the tree

B. Remove all leaf nodes from the tree

C. Convert the tree into a linked list

D. Sort the nodes in ascending order

Solution

1. Step 1: Understand the mirror operation

   Mirroring a binary tree means swapping the left and right children of every node.

2. Step 2: Apply the definition to the tree

   By swapping children at every node, the tree becomes a mirror image of the original.

3. Final Answer:

   Swap the left and right children of every node in the tree -> Option A

4. Quick Check:

   Mirror = Swap children [OK]

Hint: Mirror means swapping left and right children at all nodes [OK]

Common Mistakes:

• Thinking mirror means deleting nodes
• Confusing mirror with sorting
• Assuming mirror means flattening the tree

2. Which Go function signature correctly represents a function to mirror a binary tree node?

easy

A. func mirrorTree(root *TreeNode) int

B. func mirrorTree(root TreeNode) TreeNode

C. func mirrorTree(root TreeNode) bool

D. func mirrorTree(root *TreeNode) *TreeNode

Solution

1. Step 1: Understand pointer usage in Go trees

   Binary trees are usually represented with pointers to nodes to allow modification.

2. Step 2: Check return type for mirrored tree

   The function should return a pointer to the root of the mirrored tree.

3. Final Answer:

   func mirrorTree(root *TreeNode) *TreeNode -> Option D

4. Quick Check:

   Pointer input and output for tree nodes [OK]

Hint: Use pointers for tree nodes to modify and return [OK]

Common Mistakes:

• Passing tree nodes by value instead of pointer
• Returning wrong type like int or bool
• Not returning the mirrored tree root

3. What is the output of the following Go code that mirrors a binary tree?

type TreeNode struct {
    Val int
    Left, Right *TreeNode
}

func mirrorTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    left := mirrorTree(root.Left)
    right := mirrorTree(root.Right)
    root.Left, root.Right = right, left
    return root
}

func main() {
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    mirrorTree(root)
    fmt.Println(root.Val, root.Left.Val, root.Right.Val)
}

medium

A. 2 1 3

B. 1 2 3

C. 1 3 2

D. 3 1 2

Solution

1. Step 1: Understand the initial tree structure

   Root is 1, left child is 2, right child is 3.

2. Step 2: Apply mirrorTree function

   Mirror swaps left and right children at root, so left becomes 3 and right becomes 2.

3. Final Answer:

   1 3 2 -> Option C

4. Quick Check:

   Swapped children values = 1 3 2 [OK]

Hint: Mirror swaps left and right children recursively [OK]

Common Mistakes:

• Not swapping children correctly
• Printing values before mirroring
• Confusing left and right child values

4. Identify the error in this Go function that attempts to mirror a binary tree:

func mirrorTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    mirrorTree(root.Left)
    mirrorTree(root.Right)
    root.Left, root.Right = root.Right, root.Left
    return root
}

medium

A. The base case is missing

B. The recursive calls do not assign the mirrored subtrees back to root.Left and root.Right

C. The function returns the wrong type

D. Swapping children should happen before recursive calls

Solution

1. Step 1: Analyze recursive calls

   The function calls mirrorTree on root.Left and root.Right but ignores their returned mirrored subtrees.

2. Step 2: Check assignment of mirrored subtrees

   Without assigning returned values, the subtrees are not updated, so mirror is incomplete.

3. Final Answer:

   The recursive calls do not assign the mirrored subtrees back to root.Left and root.Right -> Option B

4. Quick Check:

   Assign returned mirrored subtrees to children [OK]

Hint: Always assign recursive results back to node children [OK]

Common Mistakes:

• Ignoring returned subtree pointers
• Swapping children before recursion
• Missing base case (though present here)

5. Given a binary tree, how would you modify the mirror function to also count how many nodes were swapped during the mirroring process?

hard

A. Add a counter variable and increment it each time left and right children are swapped recursively

B. Return the sum of node values instead of mirroring

C. Only swap nodes if their values are even

D. Use a queue to traverse the tree without recursion

Solution

1. Step 1: Understand the goal

   We want to count how many nodes had their children swapped during mirroring.

2. Step 2: Modify mirror function to count swaps

   Each time we swap left and right children at a node, increment a counter and add counts from recursive calls.

3. Final Answer:

   Add a counter variable and increment it each time left and right children are swapped recursively -> Option A

4. Quick Check:

   Count swaps during recursion [OK]

Hint: Count swaps inside recursion when swapping children [OK]

Common Mistakes:

• Counting node values instead of swaps
• Not accumulating counts from recursive calls
• Using traversal without swapping