Mirror a Binary Tree in DSA C# - Execution Trace

Concept Flow - Mirror a Binary Tree

Start at root node

↓

Swap left and right child

↓

Mirror left subtree

↓

Mirror right subtree

↓

Return mirrored subtree

↓

Done

Start at the root, swap its left and right children, then recursively mirror left and right subtrees until all nodes are processed.

Execution Sample

DSA C#

void Mirror(TreeNode node) {
  if (node == null) return;
  var temp = node.left;
  node.left = node.right;
  node.right = temp;
  Mirror(node.left);
  Mirror(node.right);
}

This code swaps left and right children of each node recursively to mirror 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	1	left=3, right=2	1 / \ 3 2 / / \ 6 4 5
3	Mirror left subtree	3	Swap left and right	3 / \ 6 null
4	Mirror left subtree	6	No children to swap	6
5	Mirror right subtree	null	None	null
6	Mirror right subtree	2	Swap left and right	2 / \ 5 4
7	Mirror left subtree	5	No children to swap	5
8	Mirror right subtree	4	No children to swap	4
9	Return to root	1	None	1 / \ 3 2 / / \ 6 5 4
10	Done	None	None	Final mirrored tree

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

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 6	Final
node	1 (root)	1 (root)	3 (left child)	2 (right child)	null (done)
node.left	2	3	6	5	null
node.right	3	2	null	4	null

Key Moments - 3 Insights

Why do we swap children before recursive calls?

Swapping children first (see Step 2) ensures that when we recursively call Mirror on node.left and node.right, we are actually mirroring the swapped subtrees, achieving the mirror effect.

What happens when a node has no children?

At leaf nodes like 6, 5, and 4 (Steps 4, 7, 8), no swap occurs because children are null, so recursion returns immediately, preserving the leaf structure.

Why do we return immediately if node is null?

Returning immediately on null nodes (Step 5) prevents errors and stops recursion at tree edges, ensuring only valid nodes are processed.

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 algorithm process node 6?

A Step 3

B Step 6

C Step 4

D Step 7

💡 Hint

Look for the Node Visited column showing node 6.

If we skip swapping children at Step 2, what happens to the final tree?

A Tree remains unchanged

B Only left subtree is mirrored

C Only right subtree is mirrored

D Tree becomes empty

💡 Hint

Swapping children is key to mirroring; see Step 2's effect on Tree State.

Concept Snapshot

Mirror a Binary Tree:
- Recursively swap left and right children of each node.
- Base case: if node is null, return.
- Swap first, then recurse on children.
- Result: tree structure flipped horizontally.
- Useful for tree transformations and symmetric checks.

Full Transcript

To mirror a binary tree, start at the root node. Swap its left and right children. Then recursively apply the same process to the left and right subtrees. If a node is null, return immediately. This process flips the tree horizontally. The execution table shows each step: starting at root, swapping children, then mirroring subtrees. Leaf nodes have no children to swap, so recursion ends there. The variable tracker shows how pointers change after swaps. Key points include swapping before recursion and stopping at null nodes. The final tree is the mirror image of the original.

Practice

1. What does mirroring a binary tree mean?

easy

A. Swapping the left and right children of every node

B. Removing all leaf nodes

C. Sorting the nodes in ascending order

D. Counting the total number of nodes

Solution

1. Step 1: Understand the mirror operation

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

2. Step 2: Identify the effect on the tree

   This operation flips the tree horizontally, creating a mirror image.

3. Final Answer:

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

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 C# method signatures correctly represents a recursive function to mirror a binary tree node named root?

easy

A. void MirrorTree(Node root)

B. int MirrorTree(Node root)

C. Node MirrorTree(Node root)

D. bool MirrorTree(Node root)

Solution

1. Step 1: Understand the purpose of the function

   The function modifies the tree in place and does not need to return a value.

2. Step 2: Choose the correct return type

   Since it changes the tree nodes directly, the return type should be void.

3. Final Answer:

   void MirrorTree(Node root) -> Option A

4. Quick Check:

   In-place change means void return [OK]

Hint: Mirror function usually returns void as it modifies tree directly [OK]

Common Mistakes:

• Returning int or bool unnecessarily
• Returning Node when not needed
• Using incorrect parameter types

3. Given the following binary tree and the C# code to mirror it, what will be the output of the inorder traversal after mirroring?

    1
   / \
  2   3
 /     \
4       5

void MirrorTree(Node root) {
  if (root == null) return;
  var temp = root.left;
  root.left = root.right;
  root.right = temp;
  MirrorTree(root.left);
  MirrorTree(root.right);
}

// Inorder traversal prints nodes in order: left, root, right

medium

A. [3, 5, 1, 4, 2]

B. [4, 2, 1, 3, 5]

C. [5, 3, 1, 2, 4]

D. [1, 2, 4, 3, 5]

Solution

1. Step 1: Mirror the tree structure

   Swap left and right children at every node:
   Original root 1: left=2, right=3 -> after mirror left=3, right=2
   Node 2: left=4, right=null -> after mirror left=null, right=4
   Node 3: left=null, right=5 -> after mirror left=5, right=null

2. Step 2: Perform inorder traversal on mirrored tree

   Inorder = left, root, right
   Start at root (1):
   Left subtree (3): left=5, right=null -> inorder: 5,3
   Root: 1
   Right subtree (2): left=null, right=4 -> inorder: 2,4
   Combined inorder: [5, 3, 1, 2, 4]

3. Final Answer:

   [5, 3, 1, 2, 4] -> Option C

4. Quick Check:

   Mirror + inorder = [5,3,1,2,4] [OK]

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

Common Mistakes:

• Not swapping children correctly
• Confusing preorder with inorder traversal
• Forgetting to mirror all nodes

4. The following C# code attempts to mirror a binary tree but does not work correctly. What is the main error?

void MirrorTree(Node root) {
  MirrorTree(root.left);
  MirrorTree(root.right);
  var temp = root.left;
  root.left = root.right;
  root.right = temp;
}

medium

A. Swapping children happens after recursive calls, causing incorrect mirror

B. Missing base case for null root

C. Using var instead of explicit type causes error

D. Function should return Node instead of void

Solution

1. Step 1: Analyze the base case

   The code lacks an if (root == null) return; check before recursing on children.

2. Step 2: Understand why this causes error

   Recursing on null children leads to NullReferenceException or stack overflow since there's no termination condition.

3. Final Answer:

   Missing base case for null root -> Option B

4. Quick Check:

   Recursion needs if(root == null) return; [OK]

Hint: Always include null base case in tree recursion [OK]

Common Mistakes:

• Omitting base case for null nodes
• Swapping after recursion instead of before
• Thinking var causes error

5. You have a binary tree where some nodes have only one child (either left or right). You want to mirror this tree using C#. Which approach correctly handles all cases including nodes with single children?

hard

A. Mirror by creating a new tree instead of modifying original

B. Only swap children if both left and right children exist

C. Swap children only at leaf nodes

D. Recursively swap left and right children if node is not null, then recurse on both children

Solution

1. Step 1: Consider nodes with single child

   Nodes with only one child still need swapping; swapping null with a child is valid.

2. Step 2: Choose recursive approach that swaps and recurses regardless of child presence

   Swapping children even if one is null ensures correct mirror. Then recurse on both children to continue mirroring.

3. Final Answer:

   Recursively swap left and right children if node is not null, then recurse on both children -> Option D

4. Quick Check:

   Swap children always, recurse both sides [OK]

Hint: Always swap children even if one is null, then recurse [OK]

Common Mistakes:

• Skipping swap when one child is null
• Swapping only leaf nodes
• Creating new tree unnecessarily