Mirror a Binary Tree in DSA Java - Execution Trace

Concept Flow - Mirror a Binary Tree

Start at root node

↓

Check if node is null?

Yes→Return null

No↓

Mirror left subtree

↓

Mirror right subtree

↓

Swap left and right children

↓

Return current node

↓

Repeat for all nodes

The process visits each node, mirrors its left and right subtrees recursively, then swaps them to create the mirror image.

Execution Sample

DSA Java

Node mirror(Node root) {
  if (root == null) return null;
  Node left = mirror(root.left);
  Node right = mirror(root.right);
  root.left = right;
  root.right = left;
  return root;
}

This code recursively mirrors a binary tree by swapping left and right children at every node.

Execution Table

Step	Operation	Node Visited	Left Subtree Mirrored	Right Subtree Mirrored	Swap Children	Tree State
1	Start at root	1	Pending	Pending	No	1 / \ 2 3
2	Mirror left subtree	2	Pending	Pending	No	1 / \ 2 3
3	Mirror left subtree	4	null	null	No	1 / \ 2 3 / 4
4	Swap children	4	null	null	No change	1 / \ 2 3 / 4
5	Mirror right subtree	5	null	null	No	1 / \ 2 3 / \ 4 5
6	Swap children	2	4	5	Yes	1 / \ 2 3 / \ 5 4
7	Mirror right subtree	3	Pending	Pending	No	1 / \ 2 3 / \ 5 4
8	Mirror left subtree	6	null	null	No	1 / \ 2 3 / \ 5 4 /
9	Mirror right subtree	7	null	null	No	1 / \ 2 3 / \ 5 4 / \ 6 7
10	Swap children	3	6	7	Yes	1 / \ 2 3 / \ 5 4 / \ 7 6
11	Swap children	1	2	3	Yes	1 / \ 3 2 / \ 7 6 / \ 5 4
12	Return mirrored root	1	Done	Done	Done	1 / \ 3 2 / \ 7 6 / \ 5 4

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

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 6	After Step 9	After Step 10	After Step 11	Final
root	1	2	2	2	2	3	1	1
left	null	4	4	5	6	7	3	3
right	null	null	5	4	7	6	2	2
Tree State	1\n/ \ 2 3	1\n/ \ 2 3\n/	1\n/ \ 2 3\n/ \	1\n/ \ 2 3\n/ \	1\n/ \ 2 3\n/ \\	1\n/ \ 2 3\n/ \\	1\n/ \ 3 2\n/ \\	1\n/ \ 3 2\n/ \\

Key Moments - 3 Insights

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

Because the recursive calls mirror the subtrees first, then swapping left and right children at the current node completes the mirror for that node. See steps 6, 10, and 11 in the execution_table.

What happens when the node is null?

The function returns null immediately, stopping recursion on that path. This is shown in steps 3 and 8 where leaf nodes have null children.

Why do we return the root node at the end?

Returning the root allows the mirrored subtree to be connected back to its parent. This is shown in step 12 where the mirrored root is returned.

Visual Quiz - 3 Questions

Look at the execution_table, what is the tree state after step 6?

A 1 with left child 2 (5 and 4 swapped), right child 3 unchanged

B 1 with left child 2 unchanged, right child 3 swapped

C 1 with left child 3, right child 2 swapped

D 1 with left child 4, right child 5 swapped

💡 Hint

Check the 'Tree State' column at step 6 in the execution_table.

At which step does the root node's children get swapped?

A Step 6

B Step 11

C Step 10

D Step 12

💡 Hint

Look for the step where 'Swap children' is 'Yes' for node 1 in the execution_table.

If the tree had only one node, how many steps would the execution_table show?

A 7 steps

B 5 steps

C 3 steps

D 1 step

💡 Hint

Think about the base case and the swap operation for a single node tree.

Concept Snapshot

Mirror a Binary Tree:
- Recursively mirror left and right subtrees
- Swap left and right children at each node
- Base case: if node is null, return null
- Returns the root of the mirrored tree
- Time complexity: O(n), n = number of nodes
- Space complexity: O(h), h = tree height (recursion stack)

Full Transcript

To mirror a binary tree, start at the root node. If the node is null, return null immediately. Otherwise, recursively mirror the left subtree and then the right subtree. After both subtrees are mirrored, swap the left and right children of the current node. Return the current node. This process repeats for every node in the tree, resulting in a mirrored tree where left and right children are swapped at all levels. The execution table shows each step visiting nodes, mirroring subtrees, swapping children, and updating the tree state. Key moments include understanding why swapping happens after recursion, handling null nodes, and returning the root node. The process runs in linear time relative to the number of nodes and uses recursion stack space proportional to the tree height.

Practice

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

easy

A. Remove all leaf nodes from the tree

B. Swap the left and right children of every node in 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 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 deleting nodes
• Confusing mirror with sorting
• Assuming mirror flattens the tree

2. Which of the following Java method signatures correctly represents a function to mirror a binary tree node?

easy

A. public void mirrorTree(Node root)

B. public int mirrorTree(Node root)

C. void mirrorTree(Node root) throws Exception

D. public Node mirrorTree()

Solution

1. Step 1: Identify correct return type

   Mirroring modifies the tree in place, so void return type is appropriate.

2. Step 2: Check method parameters

   The method should accept the root node to start mirroring from.

3. Final Answer:

   public void mirrorTree(Node root) -> Option A

4. Quick Check:

   Void return + root parameter = correct signature [OK]

Hint: Mirror modifies tree in place, so use void with root parameter [OK]

Common Mistakes:

• Using return type int instead of void
• Missing root parameter
• Adding unnecessary exceptions

3. Given the following binary tree and the mirror function below, what will be the preorder traversal output after mirroring?

    1
   / \
  2   3
 /     \
4       5

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

medium

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

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

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

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

Solution

1. Step 1: Understand the mirror function

   The function swaps left and right children at every node recursively.

2. Step 2: Apply mirror to the tree

   Original tree preorder: 1,2,4,3,5. After mirror, left and right children swap: - Root 1: left=3, right=2 - Node 3: left=5, right=null - Node 2: left=null, right=4

3. Step 3: Preorder traversal after mirror

   Visit root, then left subtree, then right subtree: 1, 3, 5, 2, 4

4. Final Answer:

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

5. Quick Check:

   Mirror swaps children; 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
• Missing recursive calls

4. The following code attempts to mirror a binary tree but causes a NullPointerException. What is the error?

public void mirrorTree(Node root) {
  Node temp = root.left;
  root.left = root.right;
  root.right = temp;
  mirrorTree(root.left);
  mirrorTree(root.right);
}

medium

A. Swapping left and right children incorrectly

B. Recursive calls should be after swapping

C. Missing null check before accessing root.left

D. Method should return a Node instead of void

Solution

1. Step 1: Identify cause of NullPointerException

   The code accesses root.left without checking if root is null.

2. Step 2: Fix by adding null check

   Adding "if (root == null) return;" at the start prevents errors when root is null.

3. Final Answer:

   Missing null check before accessing root.left -> Option C

4. Quick Check:

   NullPointerException = missing null check [OK]

Hint: Always check if node is null before accessing children [OK]

Common Mistakes:

• Ignoring null checks
• Thinking swap order causes error
• Changing return type unnecessarily

5. You have a binary tree where some nodes have only one child. After mirroring the tree using the standard mirror function, which of the following statements is true about the structure of the mirrored tree?

hard

A. Leaf nodes become internal nodes after mirroring

B. Nodes with one child will have two children after mirroring

C. The tree height will always increase by 1

D. Nodes with only left child will have only right child after mirroring

Solution

1. Step 1: Understand mirroring effect on children

   Mirroring swaps left and right children at every node.

2. Step 2: Analyze nodes with one child

   If a node has only a left child, after mirroring it will have only a right child (the left child moves to right).

3. Step 3: Check other options

   Tree height does not necessarily increase; leaf nodes remain leaves; nodes do not gain extra children.

4. Final Answer:

   Nodes with only left child will have only right child after mirroring -> Option D

5. Quick Check:

   Mirror swaps children, so left-only becomes right-only [OK]

Hint: Mirror swaps children, so single left child becomes single right child [OK]

Common Mistakes:

• Assuming tree height changes
• Thinking nodes gain extra children
• Confusing leaf and internal nodes