Mirror a Binary Tree in DSA Python

Mental Model

Flipping a binary tree means swapping every left child with its right child, making the tree look like its reflection in a mirror.

Analogy: Imagine holding a tree-shaped paper cutout in front of a mirror; the mirror image swaps left and right branches exactly.

    1
   / \
  2   3
 / \ / \
4  5 6  7

(Original tree)

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2 and right child 3; 2 has children 4 and 5; 3 has children 6 and 7

Goal: Transform the tree so that left and right children of every node are swapped, producing the mirror image

Step 1: Start at root node 1; swap its left and right children

    1
   / \
  3   2
 / \ / \
6  7 4  5

Why: Swapping children at root flips the top level branches

Step 2: Move to left child (3); swap its children 6 and 7

    1
   / \
  3   2
 / \ / \
7  6 4  5

Why: Swapping children at node 3 flips its subtree

Step 3: Move to right child (2); swap its children 4 and 5

    1
   / \
  3   2
 / \ / \
7  6 5  4

Why: Swapping children at node 2 flips its subtree

Step 4: Leaf nodes 7, 6, 5, 4 have no children, so no swaps needed

    1
   / \
  3   2
 / \ / \
7  6 5  4

Why: Leaves are base cases with no children to swap

Result:

    1
   / \
  3   2
 / \ / \
7  6 5  4

This is the mirrored binary tree.

Annotated Code

DSA Python

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

def mirror_tree(root):
    if root is None:
        return None
    # Swap left and right children
    root.left, root.right = root.right, root.left
    # Recursively mirror left subtree
    mirror_tree(root.left)
    # Recursively mirror right subtree
    mirror_tree(root.right)
    return root

def print_tree(root):
    if root is None:
        return "null"
    left_str = print_tree(root.left)
    right_str = print_tree(root.right)
    return f"{root.val} -> ({left_str}, {right_str})"

# Driver code to build tree and mirror it
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

print("Original tree:")
print(print_tree(root))

mirror_tree(root)

print("Mirrored tree:")
print(print_tree(root))

if root is None: return None

stop recursion at leaf's child (null)

root.left, root.right = root.right, root.left

swap left and right children of current node

mirror_tree(root.left)

recursively mirror left subtree after swap

mirror_tree(root.right)

recursively mirror right subtree after swap

Output

Original tree:

1 -> (2 -> (4 -> (null, null), 5 -> (null, null)), 3 -> (6 -> (null, null), 7 -> (null, null)))

Mirrored tree:

1 -> (3 -> (7 -> (null, null), 6 -> (null, null)), 2 -> (5 -> (null, null), 4 -> (null, null)))

Complexity Analysis

Time: O(n) because each node is visited once to swap children

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Iterative approaches exist but recursion is simpler and intuitive; both have similar time but iterative may use explicit stack

Edge Cases

Empty tree (root is None)

Function returns None immediately without error

DSA Python

if root is None:
    return None

Single node tree

No swaps needed; function returns the same single node

DSA Python

root.left, root.right = root.right, root.left

Tree with only left or only right children

Swapping moves children to opposite side correctly

DSA Python

root.left, root.right = root.right, root.left

When to Use This Pattern

When a problem asks to flip or reflect a binary tree structure, use the mirror tree pattern by swapping left and right children recursively.

Common Mistakes

Mistake: Swapping children after recursive calls instead of before
Fix: Swap left and right children first, then recurse on the swapped children

Mistake: Not handling the base case of null nodes causing errors
Fix: Add a base case to return immediately if the current node is None

Summary

It flips a binary tree by swapping every node's left and right children.

Use it when you need the mirror image of a binary tree.

The key is to swap children first, then recursively mirror 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