Mirror a Binary Tree in DSA C - Execution Trace

Concept Flow - Mirror a Binary Tree

Start at root node

↓

Check if node is NULL?

Yes→Return

No↓

Swap left and right child

↓

Recursively mirror left subtree

↓

Recursively mirror right subtree

↓

Return to previous call

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

Execution Sample

DSA C

void mirror(Node* root) {
  if (root == NULL) return;
  Node* temp = root->left;
  root->left = root->right;
  root->right = temp;
  mirror(root->left);
  mirror(root->right);
}

This code 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
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	Recurse left subtree of node 1 (node 3)	3	None	1 / \ 3 2 / / \ 6 4 5
4	Swap children of node 3	3	left=NULL, right=6	1 / \ 3 2 \ / \ 6 4 5
5	Recurse left subtree of node 3 (NULL)	NULL	None	No change
6	Recurse right subtree of node 3 (node 6)	6	None	No change
7	Swap children of node 6	6	left=NULL, right=NULL	No change
8	Recurse left subtree of node 6 (NULL)	NULL	None	No change
9	Recurse right subtree of node 6 (NULL)	NULL	None	No change
10	Recurse right subtree of node 1 (node 2)	2	None	1 / \ 3 2 \ / \ 6 4 5
11	Swap children of node 2	2	left=5, right=4	1 / \ 3 2 \ / \ 6 5 4
12	Recurse left subtree of node 2 (node 5)	5	None	No change
13	Swap children of node 5	5	left=NULL, right=NULL	No change
14	Recurse left subtree of node 5 (NULL)	NULL	None	No change
15	Recurse right subtree of node 5 (NULL)	NULL	None	No change
16	Recurse right subtree of node 2 (node 4)	4	None	No change
17	Swap children of node 4	4	left=NULL, right=NULL	No change
18	Recurse left subtree of node 4 (NULL)	NULL	None	No change
19	Recurse right subtree of node 4 (NULL)	NULL	None	No change
20	Return to previous calls	None	None	Final mirrored tree: 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
root	Node 1	Node 1	Node 1	Node 1	Node 1
temp	undefined	Node 2	NULL	Node 4	Node 4
root->left	Node 2	Node 3	NULL	Node 3	Node 3
root->right	Node 3	Node 2	Node 6	Node 2	Node 2

Key Moments - 3 Insights

Why do we swap the left and right children before the recursive calls?

Swapping before recursion ensures that when we recurse on root->left and root->right, we are actually processing the mirrored subtrees. See steps 2, 4, and 11 in the execution_table where swapping happens first.

What happens when the node is NULL?

When the node is NULL, the function returns immediately without doing anything. This is the base case stopping recursion, shown in steps 5, 8, 9, 14, 15, 18, and 19.

Why does the recursion visit left subtree after swapping?

Because after swapping, the original right subtree becomes the left subtree and vice versa. So recursion on root->left actually processes the original right subtree mirrored. This is clear in steps 3 and 10.

Visual Quiz - 3 Questions

Look at the execution_table, what is the left child of node 1 after step 2?

A Node 2

B Node 3

C Node 4

D NULL

💡 Hint

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

At which step does the recursion first visit a NULL node?

A Step 5

B Step 3

C Step 10

D Step 1

💡 Hint

Look for 'Node Visited' = NULL in the execution_table.

If we skip swapping children at each node, what would happen to the final tree?

A It becomes empty.

B It becomes a linked list.

C It remains unchanged (original tree).

D It becomes a full binary tree.

💡 Hint

Swapping children is the key operation to mirror; without it, the tree stays the same.

Concept Snapshot

Mirror a Binary Tree:
- Base case: if node is NULL, return
- Swap left and right children of current node
- Recursively mirror left subtree
- Recursively mirror right subtree
- Result: tree is flipped around its root

Full Transcript

To mirror a binary tree, start at the root node. If the node is NULL, return immediately. Otherwise, swap its left and right children. Then recursively apply the same process to the left and right subtrees. This swaps all nodes' children, creating a mirror image of the original tree. The recursion stops when it reaches NULL nodes. The key step is swapping children before recursive calls to ensure correct mirroring. The final tree is the original tree flipped horizontally.

Practice

1. What does mirroring a binary tree mean?

easy

A. Sorting the nodes in ascending order

B. Swapping the left and right children of every node in the tree

C. Removing all leaf nodes from the tree

D. Counting the total number of nodes in the tree

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: Identify the effect on the tree

   This operation flips the tree around its center, creating a mirror image.

3. Final Answer:

   Swapping the left and right children of every node in the tree -> Option B

4. Quick Check:

   Mirror = Swap children [OK]

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

Common Mistakes:

• Thinking mirror means sorting nodes
• Confusing mirror with deleting nodes
• Assuming mirror counts nodes

2. Which of the following is the correct C function signature to mirror a binary tree node?

easy

A. void mirrorTree(struct Node* root);

B. int mirrorTree(struct Node root);

C. struct Node mirrorTree(struct Node* root);

D. void mirrorTree(struct Node root);

Solution

1. Step 1: Understand parameter passing for trees in C

   Binary trees are usually passed as pointers to nodes to allow modification.

2. Step 2: Identify correct return type

   Mirroring modifies the tree in place, so the function returns void.

3. Final Answer:

   void mirrorTree(struct Node* root); -> Option A

4. Quick Check:

   Pointer parameter + void return = void mirrorTree(struct Node* root); [OK]

Hint: Use pointer to root and void return for in-place mirror [OK]

Common Mistakes:

• Passing struct Node by value instead of pointer
• Returning struct Node instead of void
• Using int return type incorrectly

3. What will be the output of the following code snippet after mirroring the binary tree?

struct Node {
  int data;
  struct Node* left;
  struct Node* right;
};

void mirrorTree(struct Node* root) {
  if (root == NULL) return;
  struct Node* temp = root->left;
  root->left = root->right;
  root->right = temp;
  mirrorTree(root->left);
  mirrorTree(root->right);
}

// Tree before mirror:
//     1
//    / \
//   2   3
//  /     \
// 4       5

// After mirror, print preorder traversal:
// Expected output?

medium

A. 1 2 3 4 5

B. 1 2 4 3 5

C. 1 3 2 5 4

D. 1 3 5 2 4

Solution

1. Step 1: Understand the mirror operation on the tree

   Swapping left and right children at every node flips the tree: Original root 1 has left=2, right=3 After mirror: left=3, right=2 Node 2 has left=4, right=NULL After mirror: left=NULL, right=4 Node 3 has left=NULL, right=5 After mirror: left=5, right=NULL

2. Step 2: Perform preorder traversal on mirrored tree

   Preorder: root, left, right Visit 1 Go left to 3 Go left to 5 (leaf) Back to 1, go right to 2 Go left NULL, go right 4 Sequence: 1 3 5 2 4

3. Final Answer:

   1 3 5 2 4 -> Option D

4. Quick Check:

   Mirror + preorder = 1 3 5 2 4 [OK]

Hint: Mirror swaps children; preorder visits root-left-right [OK]

Common Mistakes:

• Not swapping children correctly
• Confusing preorder with inorder or postorder
• Missing leaf nodes in traversal

4. Identify the error in the following mirror function and select the fix:

void mirrorTree(struct Node* root) {
  if (root == NULL) return;
  mirrorTree(root->left);
  struct Node* temp = root->left;
  root->left = root->right;
  root->right = temp;
  mirrorTree(root->right);
}

medium

A. Add return type as int instead of void

B. Remove the base case check for NULL

C. Swap children before recursive calls to mirrorTree

D. Change temp to int instead of struct Node*

Solution

1. Step 1: Analyze the order of operations in the function

   The function calls mirrorTree on left and right children before swapping them. This causes the recursive calls to work on original children, not swapped ones.

2. Step 2: Correct the order to swap first, then recurse

   Swapping children first ensures recursive calls mirror the swapped subtrees correctly.

3. Final Answer:

   Swap children before recursive calls to mirrorTree -> Option C

4. Quick Check:

   Swap first, recurse later [OK]

Hint: Swap children before recursion to mirror correctly [OK]

Common Mistakes:

• Swapping after recursion causes incorrect mirror
• Removing base case causes crashes
• Changing temp type breaks pointer logic

5. Given a binary tree where some nodes have only one child, what is the effect of mirroring the tree on the structure and leaf nodes? Choose the correct statement.

hard

A. All leaf nodes remain leaf nodes but their positions are mirrored

B. Some leaf nodes become internal nodes after mirroring

C. The number of leaf nodes doubles after mirroring

D. Mirroring removes all nodes with only one child

Solution

1. Step 1: Understand mirroring effect on node positions

   Mirroring swaps left and right children but does not add or remove nodes. Leaf nodes remain leaf nodes but their positions flip left to right.

2. Step 2: Confirm leaf nodes count and structure

   Number of leaf nodes stays the same; no nodes become internal or are removed. Only their left-right positions change.

3. Final Answer:

   All leaf nodes remain leaf nodes but their positions are mirrored -> Option A

4. Quick Check:

   Mirror flips positions, leaf count unchanged [OK]

Hint: Mirror flips positions, leaf nodes stay leaf nodes [OK]

Common Mistakes:

• Thinking leaf nodes become internal nodes
• Assuming nodes are added or removed
• Believing leaf count changes