Mirror a Binary Tree in DSA C++ - Execution Trace

Concept Flow - Mirror a Binary Tree

Start at root node

↓

Swap left and right child

↓

Recursively mirror left subtree

↓

Recursively mirror right subtree

↓

Return mirrored subtree

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

Execution Sample

DSA C++

void mirror(Node* root) {
  if (!root) return;
  swap(root->left, root->right);
  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
2	Swap children	1	left=3, right=2	1 / \ 3 2
3	Recurse left subtree	3	None	3 / \ 6 7
4	Swap children	3	left=7, right=6	3 / \ 7 6
5	Recurse left subtree	7	None	7 (leaf)
6	Recurse right subtree	6	None	6 (leaf)
7	Recurse right subtree of root	2	None	2 / \ 4 5
8	Swap children	2	left=5, right=4	2 / \ 5 4
9	Recurse left subtree	5	None	5 (leaf)
10	Recurse right subtree	4	None	4 (leaf)
11	Return to root	1	None	1 / \ 3 2 / \ / \ 7 6 5 4

💡 All nodes visited and children swapped, tree is fully mirrored.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 8	Final
root	Node 1	Node 1	Node 1	Node 1	Node 1
current node	Node 1	Node 3	Node 7	Node 2	Node 1
left child of current	Node 2	Node 7	None	Node 5	Node 3
right child of current	Node 3	Node 6	None	Node 4	Node 2
tree structure	1->2,3; 2->4,5; 3->6,7	1->3,2; 3->7,6; 2->4,5	3->7,6; 7 leaf; 6 leaf	2->5,4; 5 leaf; 4 leaf	1->3,2; 3->7,6; 2->5,4

Key Moments - 3 Insights

Why do we swap children before recursive calls?

Swapping children first (see Step 2) ensures that when recursion goes to left and right subtrees, it processes the new mirrored positions, correctly flipping the whole tree.

What happens when a node is a leaf?

At leaf nodes (Steps 5, 6, 9, 10), there are no children to swap, so recursion returns immediately, stopping further calls.

Why do we check if the node is null at the start?

The base case (Step 1) prevents recursion on empty nodes, avoiding errors and stopping recursion when reaching beyond leaves.

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 Node 5

💡 Hint

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

At which step does the recursion visit node 7?

A Step 5

B Step 4

C Step 3

D Step 6

💡 Hint

Look at the 'Node Visited' column to find when node 7 is processed.

If we skip swapping children at each node, how would the final tree state change?

A Tree becomes empty

B Only leaf nodes swap

C Tree remains unchanged

D Tree becomes a linked list

💡 Hint

Refer to the 'Operation' column and understand the role of swapping in mirroring.

Concept Snapshot

Mirror a Binary Tree:
- Swap left and right child of each node
- Recursively apply to left and right subtrees
- Base case: if node is null, return
- Result: tree flipped around its root
- Common use: image reflection, tree transformations

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 subtree and the right subtree. If a node is null, stop recursion. This process flips the tree around its root, creating a mirror image. The code swaps children first, then recurses, ensuring the entire tree is mirrored correctly. Leaf nodes have no children to swap, so recursion ends there. This method is simple and effective for tree transformations.

Practice

1. What does mirroring a binary tree mean?

easy

A. Sorting the nodes in ascending order

B. Reversing the order of nodes in each level

C. Swapping the left and right children of every node

D. Deleting all leaf nodes

Solution

1. Step 1: Understand the mirror operation

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

2. Step 2: Clarify what happens to nodes

   Each node's left child becomes its right child and vice versa, recursively.

3. Final Answer:

   Swapping the left and right children of every node -> Option C

4. Quick Check:

   Mirror = Swap children [OK]

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

Common Mistakes:

• Thinking mirror means reversing node values
• Confusing mirror with tree traversal order
• Assuming mirror deletes nodes

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

easy

A. void mirror(Node* root)

B. int mirror(Node root)

C. Node mirror(Node* root)

D. void mirror(Node root)

Solution

1. Step 1: Identify correct parameter type

   The function should take a pointer to the root node to modify the tree in place.

2. Step 2: Identify correct return type

   Since the tree is modified in place, the function can return void.

3. Final Answer:

   void mirror(Node* root) -> Option A

4. Quick Check:

   Pointer param + void return = void mirror(Node* root) [OK]

Hint: Use pointer parameter and void return for in-place tree changes [OK]

Common Mistakes:

• Passing node by value instead of pointer
• Returning Node instead of void
• Using incorrect parameter types

3. What is the output of the following code after mirroring the binary tree?

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

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

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

Node* root = new Node{1, new Node{2, new Node{4, nullptr, nullptr}, nullptr}, new Node{3, nullptr, new Node{5, nullptr, nullptr}}};
mirror(root);
// Print inorder traversal
void inorder(Node* node) {
  if (!node) return;
  inorder(node->left);
  std::cout << node->data << " ";
  inorder(node->right);
}
inorder(root);

medium

A. 5 3 1 4 2

B. 5 3 1 2 4

C. 1 2 4 3 5

D. 4 2 1 3 5

Solution

1. Step 1: Understand the original tree and inorder traversal

   Original inorder: left-root-right = 4 2 1 3 5

2. Step 2: Mirror swaps left and right children recursively

   Mirrored tree structure: 1 / \ 3 2 / \ 5 4 Inorder traversal now: 5 3 1 2 4

3. Final Answer:

   5 3 1 2 4 -> Option B

4. Quick Check:

   Inorder mirrored = 5 3 1 2 4 [OK]

Hint: Mirror swaps children; inorder reverses left-right order [OK]

Common Mistakes:

• Not swapping children correctly
• Confusing preorder with inorder traversal
• Printing original tree instead of mirrored

4. Identify the error in this mirror function and choose the fix:

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

medium

A. Swap root->left and root->right before recursive calls

B. Change 'if (root == nullptr)' to 'if (!root->left && !root->right)'

C. Add 'delete temp;' after swapping

D. Function should return void, remove 'return root;'

Solution

1. Step 1: Check function return type and usage

   The function is declared void but tries to return root pointer, which causes a compile error.

2. Step 2: Fix by removing the return statement

   Since the tree is modified in place, no return is needed; remove 'return root;'.

3. Final Answer:

   Function should return void, remove 'return root;' -> Option D

4. Quick Check:

   Void function must not return value [OK]

Hint: Void functions should not return values [OK]

Common Mistakes:

• Returning value from void function
• Changing base case incorrectly
• Deleting nodes unnecessarily

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. Return the number of nodes from the function and sum left and right counts

B. Add a counter parameter and increment it each time children are swapped

C. Use a global variable to count swaps inside the mirror function

D. Count nodes before and after mirroring and subtract counts

Solution

1. Step 1: Understand counting swaps during recursion

   Each node swap can be counted by returning 1 plus counts from left and right subtrees.

2. Step 2: Modify mirror to return int and sum counts

   Return 0 if node is null; else return 1 + mirror(left) + mirror(right).

3. Final Answer:

   Return the number of nodes from the function and sum left and right counts -> Option A

4. Quick Check:

   Return counts from recursion to sum swaps [OK]

Hint: Return counts from recursion to sum swapped nodes [OK]

Common Mistakes:

• Using global variables causing side effects
• Counting nodes before and after mirroring (no change)
• Not accumulating counts correctly