Mirror a Binary Tree in DSA Python - Deep Dive

Overview - Mirror a Binary Tree

What is it?

Mirroring a binary tree means swapping the left and right children of every node in the tree. This creates a new tree that looks like the original tree flipped around its center. It is like looking at the tree in a mirror. The structure remains the same but the positions of nodes are reversed.

Why it matters

Mirroring a binary tree helps us understand tree transformations and symmetry. It is useful in problems where we want to reverse or invert tree structures, such as image processing, graphical transformations, or checking if two trees are mirror images. Without this concept, we would struggle to manipulate tree shapes efficiently.

Where it fits

Before learning to mirror a binary tree, you should understand what a binary tree is and how to traverse it (like preorder, inorder, or postorder). After mastering mirroring, you can explore tree symmetry checks, tree rotations, and more complex tree algorithms like balancing or serialization.

Mental Model

Core Idea

Mirroring a binary tree means swapping every node's left and right children recursively until the entire tree is flipped.

Think of it like...

Imagine holding a family tree drawing and flipping it horizontally so that all left branches become right branches and vice versa, like looking at it through a mirror.

Original Tree:           Mirrored Tree:
    1                         1
   / \                       / \
  2   3                     3   2
 / \   \                   /   / \
4   5   6                 6   5   4

Build-Up - 6 Steps

1

Foundation

Understanding Binary Tree Structure

Concept: Learn what a binary tree is and how nodes connect with left and right children.

A binary tree is a structure where each node has up to two children: left and right. Each child is itself a node or empty (null). For example, a node with value 1 might have a left child 2 and right child 3.

Result

You can visualize and represent a binary tree with nodes connected by left and right links.

Understanding the basic structure of a binary tree is essential before changing or manipulating it.

2

Foundation

Traversing a Binary Tree Recursively

Concept: Learn how to visit each node in a tree using recursion.

Recursion means a function calls itself to handle smaller parts. For a tree, you visit a node, then recursively visit its left child, then its right child. This helps process every node systematically.

Result

You can write code that touches every node in the tree without missing any.

Recursion is a natural way to explore trees because trees are defined recursively.

3

Intermediate

Swapping Left and Right Children

🤔Before reading on: Do you think swapping children at only the root node mirrors the whole tree or just the top?

Concept: Swapping the left and right children of a node flips that node's immediate branches.

At any node, exchange its left child with its right child. This changes the node's immediate structure but does not affect deeper nodes unless you repeat the process there.

Result

Only the current node's children are swapped, so the tree is partially mirrored at that node.

Swapping children at one node is a small step; full mirroring requires doing this at every node.

4

Intermediate

Recursively Mirroring the Entire Tree

🤔Before reading on: Do you think mirroring the left subtree first or the right subtree first changes the final mirrored tree?

Concept: To mirror the whole tree, recursively mirror left and right subtrees, then swap them at each node.

For each node, first mirror its left subtree, then its right subtree, then swap these two subtrees. This ensures the entire tree is flipped correctly.

Result

The entire tree becomes a mirror image of the original, with all left and right children swapped at every level.

Recursion combined with swapping at each node achieves a complete mirror transformation.

5

Advanced

Implementing Mirror Function in Python

🤔Before reading on: Will the mirror function change the original tree or create a new mirrored tree?

Concept: Write a Python function that modifies the tree in place by recursively swapping children.

Define a function mirror(node) that: - If node is None, return None. - Recursively call mirror on node.left and node.right. - Swap node.left and node.right. - Return the node. This changes the original tree to its mirror.

Result

The original tree structure is flipped in place without creating a new tree.

In-place modification saves memory and is efficient for large trees.

6

Expert

Handling Edge Cases and Performance

🤔Before reading on: Does mirroring a tree with only left children produce a tree with only right children?

Concept: Consider trees with missing children, single nodes, or very deep trees and analyze performance.

If a node has only one child, mirroring moves it to the opposite side. For very deep trees, recursion depth might be a concern. Iterative approaches or tail recursion optimization can help. Also, mirroring a tree twice returns it to original form.

Result

Mirroring works correctly for all tree shapes, but very deep trees may need special handling to avoid stack overflow.

Understanding edge cases and recursion limits is crucial for robust, production-ready code.

Under the Hood

Mirroring works by recursively visiting each node and swapping its left and right pointers. The recursion stack keeps track of nodes to process. Each swap changes the node's immediate children, and recursion ensures all nodes are processed. The tree nodes are references in memory, so swapping pointers changes the tree structure directly.

Why designed this way?

Recursion matches the tree's recursive nature, making the code simple and elegant. Swapping pointers in place avoids extra memory use. Alternatives like iterative methods exist but are more complex. This design balances clarity and efficiency.

Start
  ↓
Visit Node
  ↓
Mirror Left Subtree ←─────┐
  ↓                      │
Mirror Right Subtree ─────┤
  ↓                      │
Swap Left and Right       │
  ↓                      │
Return Node ──────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does mirroring a tree create a new tree or modify the original? Commit to your answer.

Common Belief: Mirroring creates a completely new tree with new nodes.

Reality: Mirroring usually modifies the original tree by swapping pointers; it does not create new nodes.

Why it matters: Thinking it creates a new tree can lead to unnecessary memory use and confusion about the tree's identity.

Quick: If you mirror a tree twice, does it return to the original? Commit yes or no.

Common Belief: Mirroring twice does not restore the original tree.

Reality: Mirroring a tree twice returns it exactly to its original shape.

Why it matters: Knowing this helps in algorithms that require toggling between normal and mirrored states efficiently.

Quick: Does the order of mirroring left or right subtree first affect the final mirrored tree? Commit your answer.

Common Belief: Mirroring left subtree before right subtree changes the final mirrored tree.

Reality: The order does not affect the final mirrored tree because both subtrees are mirrored before swapping.

Why it matters: Misunderstanding this can cause unnecessary complexity or incorrect assumptions in implementation.

Quick: Can mirroring a tree fix an unbalanced tree? Commit yes or no.

Common Belief: Mirroring a tree balances it automatically.

Reality: Mirroring only flips the tree; it does not balance or change the height or shape in a way that balances it.

Why it matters: Confusing mirroring with balancing can lead to wrong solutions in tree optimization problems.

Expert Zone

1

Mirroring is an involution: applying it twice returns the original tree, which can be used to toggle states efficiently.

2

In languages without automatic memory management, careful pointer swapping is needed to avoid memory leaks or dangling pointers.

3

Iterative mirroring using a stack or queue can avoid recursion limits but requires explicit data structures and careful state management.

When NOT to use

Mirroring is not suitable when you need to preserve the original tree structure intact; in such cases, create a mirrored copy instead. Also, for balancing trees or optimizing search, use rotations or balancing algorithms like AVL or Red-Black trees instead.

Production Patterns

Mirroring is used in graphical applications to flip images represented as trees, in algorithms checking tree symmetry, and in interview problems testing recursive tree manipulation skills. It also appears in serialization/deserialization tasks where mirrored trees represent alternative data views.

Connections

Tree Traversals

Mirroring builds on recursive tree traversal techniques.

Understanding traversal orders helps grasp how mirroring visits and modifies every node.

Involution Functions in Mathematics

Mirroring is an involution, a function that is its own inverse.

Recognizing mirroring as an involution connects computer science with mathematical function properties, enriching understanding of reversible operations.

Image Flipping in Computer Graphics

Mirroring a binary tree is analogous to flipping an image horizontally.

Knowing how images are flipped helps understand the practical impact of mirroring tree structures representing graphical data.

Common Pitfalls

#1 Trying to mirror the tree without recursion or iteration, only swapping the root's children.

Wrong approach:

def mirror(node):
if node is None:
return
node.left, node.right = node.right, node.left
# No recursive calls

Correct approach:

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

Root cause:

Not realizing that all nodes must be processed, not just the root.

#2 Creating new nodes instead of swapping pointers, leading to duplicated trees and memory waste.

Wrong approach:

def mirror(node):
if node is None:
return None
new_node = TreeNode(node.val)
new_node.left = mirror(node.right)
new_node.right = mirror(node.left)
return new_node

Correct approach:

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

Root cause:

Confusing mirroring with creating a mirrored copy; not understanding in-place modification.

#3 Ignoring base case and causing infinite recursion or errors on empty nodes.

Wrong approach:

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

Correct approach:

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

Root cause:

Not handling the None (empty) nodes properly in recursion.

Key Takeaways

Mirroring a binary tree means swapping every node's left and right children recursively to flip the tree.

Recursion is the natural and simplest way to visit and modify all nodes in the tree for mirroring.

Mirroring modifies the original tree in place unless explicitly coded to create a new tree.

Mirroring is an involution: applying it twice restores the original tree structure.

Understanding mirroring helps in problems involving tree symmetry, graphical transformations, and recursive data manipulation.

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