Mirror a Binary Tree in DSA Python - Execution Trace

Concept Flow - Mirror a Binary Tree

Start at root node

↓

Swap left and right child

↓

Move to left child (original right)

↓

Repeat swap recursively

↓

Move to right child (original left)

↓

Repeat swap recursively

↓

Return when node is None

↓

All nodes processed - Tree mirrored

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

Execution Sample

DSA Python

def mirror(node):
    if node is None:
        return
    node.left, node.right = node.right, node.left
    mirror(node.left)
    mirror(node.right)

This code swaps the 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	Recurse left child	3	None	1 / \ 3 2 / / \ 6 4 5
4	Swap children	3	left=None, right=6	1 / \ 3 2 \ / \ 6 4 5
5	Recurse left child	None	None	No change
6	Recurse right child	6	None	1 / \ 3 2 \ / \ 6 4 5
7	Swap children	6	left=None, right=None	No change
8	Recurse left child	None	None	No change
9	Recurse right child	None	None	No change
10	Recurse right child of root	2	None	1 / \ 3 2 \ / \ 6 4 5
11	Swap children	2	left=5, right=4	1 / \ 3 2 \ / \ 6 5 4
12	Recurse left child	5	None	1 / \ 3 2 \ / \ 6 5 4
13	Swap children	5	left=None, right=None	No change
14	Recurse left child	None	None	No change
15	Recurse right child	None	None	No change
16	Recurse right child	4	None	1 / \ 3 2 \ / \ 6 5 4
17	Swap children	4	left=None, right=None	No change
18	Recurse left child	None	None	No change
19	Recurse right child	None	None	No change
20	All nodes processed	None	None	1 / \ 3 2 \ / \ 6 5 4

💡 Recursion ends when all nodes are None and all swaps are done.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 7	After Step 11	Final
node	1 (root)	1 (root)	3 (left child of root)	6 (right child of 3)	2 (right child of root)	None (end)
node.left	2	3	None	None	5	None
node.right	3	2	6	None	4	None
Tree State	Original tree	Root children swapped	Left subtree mirrored	Leaf node 6 processed	Right subtree children swapped	Fully mirrored tree

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, we mirror the new left and right subtrees correctly. See steps 2 and 4 in execution_table where swap happens before recursion.

What happens when the node is None?

When node is None, recursion stops for that path (steps 5, 8, 15, 18, 19). This prevents errors and ends recursion on leaf nodes.

Why does the tree state change visually after each swap?

Each swap changes the pointers of the node's children, which changes the tree structure. This is shown in the Tree State column in execution_table after steps 2, 4, and 11.

Visual Quiz - 3 Questions

Look at the execution_table at step 2. What are the left and right children of node 1 after the swap?

A left=2, right=3

B left=4, right=5

C left=3, right=2

D left=None, right=None

💡 Hint

Check the Pointer Changes column at step 2 in execution_table.

At which step does the recursion first reach a None node?

A Step 10

B Step 5

C Step 7

D Step 12

💡 Hint

Look for 'Node Visited' = None in execution_table rows.

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

A The tree would remain the same as original

B The tree would be fully mirrored

C Only leaf nodes would swap

D The tree would become empty

💡 Hint

Refer to the Tree State column in execution_table showing changes after swaps.

Concept Snapshot

Mirror a Binary Tree:
- Swap left and right children of each node
- Do this recursively for all nodes
- Base case: node is None
- Result: tree structure reversed left-to-right
- Use recursion to visit all nodes

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 children. If a node is None, stop recursion on that path. This process continues until all nodes have their children swapped, resulting in a mirrored tree. The code swaps children before recursive calls to ensure correct mirroring. The recursion ends when all nodes are processed. The tree visually changes after each swap, reversing the left and right subtrees.

Practice

1. What does mirroring a binary tree mean?
Mirror a Binary Tree means:

easy

A. Swapping the left and right children of every node

B. Deleting all leaf nodes

C. Reversing the values of nodes in each level

D. Sorting 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 in the tree.

2. Step 2: Compare with other options

   Deleting leaves, reversing values, or sorting nodes are different operations and do not create 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 reversing node values only
• Confusing mirror with tree traversal
• Assuming mirror deletes nodes

2. Which of the following is the correct Python function header to define a recursive mirror function for a binary tree node named root?

easy

A. def mirror(root):

B. def mirror(root) -> int:

C. def mirror(root) -> None:

D. def mirror(root) -> str:

Solution

1. Step 1: Identify function purpose and return type

   The mirror function modifies the tree in place and returns nothing, so return type is None.

2. Step 2: Check syntax correctness

   def mirror(root) -> None: uses correct Python syntax with type hint for no return value.

3. Final Answer:

   def mirror(root) -> None: -> Option C

4. Quick Check:

   Function returns nothing = None [OK]

Hint: Mirror modifies tree, returns nothing, so use -> None [OK]

Common Mistakes:

• Using wrong return type like int or str
• Omitting parentheses in function definition
• Missing colon at end of function header

3. What will be the output of the following code after calling mirror(root)? Assume the tree is:
1
/ \
2 3

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def mirror(root) -> None:
    if root is None:
        return
    root.left, root.right = root.right, root.left
    mirror(root.left)
    mirror(root.right)

root = Node(1)
root.left = Node(2)
root.right = Node(3)
mirror(root)
print(root.left.val, root.right.val)

medium

A. 1 3

B. 3 2

C. 2 3

D. 3 1

Solution

1. Step 1: Understand initial tree structure

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

2. Step 2: Apply mirror function

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

3. Final Answer:

   3 2 -> Option B

4. Quick Check:

   Swapped children = 3 2 [OK]

Hint: Mirror swaps children, so left=3 and right=2 after mirror [OK]

Common Mistakes:

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

4. Find the error in this mirror function code:

def mirror(root):
    if root is None:
        return
    mirror(root.left)
    mirror(root.right)
    root.left = root.right
    root.right = root.left

medium

A. Swapping left and right children is done incorrectly

B. Base case is missing

C. Function does not call itself recursively

D. No return statement in function

Solution

1. Step 1: Analyze swapping logic

   Assigning root.left = root.right then root.right = root.left sets both to same child, losing original left.

2. Step 2: Correct swapping method

   Use simultaneous swap: root.left, root.right = root.right, root.left to avoid overwriting.

3. Final Answer:

   Swapping left and right children is done incorrectly -> Option A

4. Quick Check:

   Swap must be simultaneous to avoid overwrite [OK]

Hint: Swap children simultaneously to avoid overwriting [OK]

Common Mistakes:

• Swapping children one by one causing data loss
• Forgetting base case for recursion
• Not swapping children at all

5. Given a binary tree, write a function to check if the tree is symmetric (a mirror of itself). Which approach correctly uses the mirror concept?

hard

A. Traverse tree in preorder and compare with inorder traversal

B. Check if left and right subtrees have the same number of nodes

C. Check if all node values are equal in left and right subtrees

D. Compare left subtree with right subtree by recursively checking if left.left matches right.right and left.right matches right.left

Solution

1. Step 1: Understand symmetry in binary trees

   A symmetric tree is a mirror of itself, so left subtree must mirror right subtree.

2. Step 2: Use recursive comparison

   Check if left.left matches right.right and left.right matches right.left recursively to confirm mirror symmetry.

3. Final Answer:

   Compare left subtree with right subtree by recursively checking if left.left matches right.right and left.right matches right.left -> Option D

4. Quick Check:

   Symmetry = recursive mirror check [OK]

Hint: Symmetry means left subtree mirrors right subtree recursively [OK]

Common Mistakes:

• Only comparing node counts, not structure
• Comparing node values without structure
• Using traversal orders that don't check mirror