Mirror a Binary Tree in DSA C - 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 is a mirror image of the original. The structure stays the same, but the positions of nodes are flipped horizontally. It is a simple transformation that changes the tree's shape but not its values.

Why it matters

Mirroring a binary tree helps understand tree structures and recursive thinking. It is used in image processing, symmetric data checks, and algorithms that require tree transformations. Without this concept, programmers would struggle to manipulate tree shapes or solve problems involving symmetry. It also builds a foundation for more complex tree operations.

Where it fits

Before learning this, you should understand what a binary tree is and how to traverse it. After mastering mirroring, you can explore tree rotations, balancing trees, and advanced tree algorithms like AVL or Red-Black trees.

Mental Model

Core Idea

Mirroring a binary tree means swapping every node's left and right children to create a horizontally flipped version of the tree.

Think of it like...

Imagine holding a family photo and flipping it over a vertical mirror line so the left side becomes the right side and vice versa.

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 can be another node or empty (null). For example, a node with value 1 can have left child 2 and right child 3. This forms a branching structure.

Result

You can visualize and represent trees with nodes and their left/right links.

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

2

Foundation

Traversing a Binary Tree Recursively

Concept: Learn how to visit each node using recursion, a key technique for tree operations.

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

Result

You can write code that visits all nodes in a tree without loops.

Recursion matches the tree's branching nature, making complex operations simpler.

3

Intermediate

Swapping Children to Mirror Nodes

🤔Before reading on: do you think swapping children at just the root node mirrors the whole tree or only the top level? Commit to your answer.

Concept: Mirroring requires swapping left and right children at every node, not just the root.

To mirror a tree, at each node, swap its left and right children. Then, recursively do the same for each child node. This ensures the entire tree flips horizontally, not just the top node.

Result

The tree becomes a mirror image with left and right sides flipped at every level.

Knowing that mirroring is a recursive process prevents partial or incorrect transformations.

4

Intermediate

Implementing Mirror Function in C

🤔Before reading on: do you think the mirror function should return a new tree or modify the original tree in place? Commit to your answer.

Concept: The mirror function can modify the original tree by swapping children pointers recursively.

In C, define a function that takes a node pointer. If the node is null, return. Otherwise, swap its left and right pointers, then call the function recursively on both children. This changes the tree in place without extra memory.

Result

The original tree structure is changed to its mirror image after the function runs.

Modifying the tree in place is memory efficient and matches common C programming practices.

5

Advanced

Handling Edge Cases and Null Nodes

🤔Before reading on: do you think null children need special handling in the mirror function or can be ignored? Commit to your answer.

Concept: Null children must be checked to avoid errors during recursion.

When mirroring, always check if a node or its children are null before swapping or recursing. This prevents accessing invalid memory and crashes. The base case for recursion is when the node is null.

Result

The mirror function safely handles empty trees and leaf nodes without errors.

Proper null checks ensure robustness and prevent runtime failures.

6

Expert

Mirror Function Performance and Stack Usage

🤔Before reading on: do you think mirroring a very deep tree risks running out of stack space? Commit to your answer.

Concept: Recursive mirror functions use stack space proportional to tree height, which can cause stack overflow on deep trees.

Each recursive call adds a frame to the call stack. For very deep or unbalanced trees, this can exhaust stack memory. Iterative approaches with explicit stacks or tail recursion optimizations can reduce this risk.

Result

Understanding recursion limits helps write safer code for large trees.

Knowing recursion's memory cost guides better design choices for production systems.

Under the Hood

The mirror function works by recursively visiting each node. At each node, it swaps the pointers to the left and right children. This pointer swap changes the tree's shape in memory. The recursion unwinds after all nodes have been processed, resulting in a fully mirrored tree. The process uses the call stack to remember nodes yet to be processed.

Why designed this way?

Recursion naturally fits tree structures because trees branch like recursive calls. Swapping pointers in place avoids extra memory use. This design is simple, efficient, and easy to implement in languages like C. Alternatives like iterative methods exist but are more complex.

Start
  ↓
Visit Node
  ↓
Is Node NULL? -- Yes -> Return
  ↓ No
Swap Left and Right Pointers
  ↓
Recurse Left Child
  ↓
Recurse Right Child
  ↓
Return
End

Myth Busters - 4 Common Misconceptions

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

Common Belief: Mirroring always creates a new tree and leaves the original unchanged.

Reality: Most mirror functions modify the original tree in place by swapping pointers.

Why it matters: Assuming a new tree is created wastes memory and can cause confusion about which tree is used later.

Quick: Is swapping children at the root enough to mirror the whole tree? Commit to your answer.

Common Belief: Swapping only the root's children mirrors the entire tree.

Reality: Only swapping the root's children flips the top level; all nodes must be swapped recursively for a full mirror.

Why it matters: Partial mirroring leads to incorrect tree shapes and bugs in algorithms relying on full symmetry.

Quick: Can mirroring a tree be done without recursion? Commit to your answer.

Common Belief: Mirroring must be done recursively; iteration is not possible.

Reality: Mirroring can be done iteratively using a stack or queue to traverse nodes and swap children.

Why it matters: Knowing iterative methods helps avoid stack overflow in very deep trees.

Quick: Does mirroring change the values stored in nodes? Commit to your answer.

Common Belief: Mirroring changes the values inside the nodes to reflect the mirror image.

Reality: Mirroring only swaps the positions (pointers) of nodes; node values remain unchanged.

Why it matters: Confusing value changes with pointer swaps can cause incorrect assumptions about data integrity.

Expert Zone

1

Mirroring a tree in place is efficient but destroys the original structure; cloning before mirroring is needed if preservation is required.

2

Tail recursion optimization can reduce stack usage in some compilers, but C often lacks guaranteed support, so iterative methods may be safer.

3

In threaded binary trees or trees with parent pointers, mirroring requires careful pointer updates beyond just left and right children.

When NOT to use

Avoid in-place mirroring when the original tree must be preserved; instead, create a mirrored copy. For very deep or unbalanced trees, use iterative mirroring to prevent stack overflow. If the tree has extra pointers (like parent links), use specialized algorithms to maintain consistency.

Production Patterns

Mirroring is used in graphics for flipping scene graphs, in symmetric data validation, and in algorithms that require tree transformations like expression tree manipulations. Production code often combines mirroring with cloning and uses iterative approaches for stability.

Connections

Tree Traversal

Mirroring builds on recursive tree traversal techniques.

Understanding traversal patterns is essential to visit and modify every node correctly during mirroring.

Graph Isomorphism

Mirroring is a special case of graph transformation preserving node values but changing structure.

Knowing mirroring helps understand how graph structures can be transformed while preserving certain properties.

Symmetry in Physics

Mirroring a tree is analogous to symmetry operations in physics that flip spatial configurations.

Recognizing symmetry transformations in data structures connects computer science with physical concepts of balance and invariance.

Common Pitfalls

#1 Ignoring null checks causes crashes.

Wrong approach:

void mirror(Node* root) {
Node* temp = root->left;
root->left = root->right;
root->right = temp;
mirror(root->left);
mirror(root->right);
}

Correct approach:

void mirror(Node* root) {
if (root == NULL) return;
Node* temp = root->left;
root->left = root->right;
root->right = temp;
mirror(root->left);
mirror(root->right);
}

Root cause:

Not checking for null nodes before accessing pointers leads to dereferencing null and runtime errors.

#2 Swapping children only at root misses deeper nodes.

Wrong approach:

void mirror(Node* root) {
if (root == NULL) return;
Node* temp = root->left;
root->left = root->right;
root->right = temp;
}

Correct approach:

void mirror(Node* root) {
if (root == NULL) return;
Node* temp = root->left;
root->left = root->right;
root->right = temp;
mirror(root->left);
mirror(root->right);
}

Root cause:

Forgetting to recurse means only the top node is mirrored, leaving the rest unchanged.

#3 Creating a new tree unnecessarily wastes memory.

Wrong approach:

Node* mirror(Node* root) {
if (root == NULL) return NULL;
Node* newNode = malloc(sizeof(Node));
newNode->data = root->data;
newNode->left = mirror(root->right);
newNode->right = mirror(root->left);
return newNode;
}

Correct approach:

void mirror(Node* root) {
if (root == NULL) return;
Node* temp = root->left;
root->left = root->right;
root->right = temp;
mirror(root->left);
mirror(root->right);
}

Root cause:

Unnecessary copying increases memory use and complexity when in-place modification suffices.

Key Takeaways

Mirroring a binary tree flips it horizontally by swapping left and right children at every node.

Recursion is the natural and simplest way to visit all nodes and perform the swaps.

Always check for null nodes to avoid errors during recursion.

In-place mirroring modifies the original tree efficiently but destroys its original shape.

Understanding mirroring deepens your grasp of tree structures and recursive algorithms.

Practice

1. What does mirroring a binary tree mean?

easy

A. Sorting the nodes in ascending order

B. Swapping the left and right children of every node in the tree

C. Removing all leaf nodes from the tree

D. Counting the total number of nodes in the tree

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: Identify the effect on the tree

   This operation flips the tree around its center, creating a mirror image.

3. Final Answer:

   Swapping 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 sorting nodes
• Confusing mirror with deleting nodes
• Assuming mirror counts nodes

2. Which of the following is the correct C function signature to mirror a binary tree node?

easy

A. void mirrorTree(struct Node* root);

B. int mirrorTree(struct Node root);

C. struct Node mirrorTree(struct Node* root);

D. void mirrorTree(struct Node root);

Solution

1. Step 1: Understand parameter passing for trees in C

   Binary trees are usually passed as pointers to nodes to allow modification.

2. Step 2: Identify correct return type

   Mirroring modifies the tree in place, so the function returns void.

3. Final Answer:

   void mirrorTree(struct Node* root); -> Option A

4. Quick Check:

   Pointer parameter + void return = void mirrorTree(struct Node* root); [OK]

Hint: Use pointer to root and void return for in-place mirror [OK]

Common Mistakes:

• Passing struct Node by value instead of pointer
• Returning struct Node instead of void
• Using int return type incorrectly

3. What will be the output of the following code snippet after mirroring the binary tree?

struct Node {
  int data;
  struct Node* left;
  struct Node* right;
};

void mirrorTree(struct Node* root) {
  if (root == NULL) return;
  struct Node* temp = root->left;
  root->left = root->right;
  root->right = temp;
  mirrorTree(root->left);
  mirrorTree(root->right);
}

// Tree before mirror:
//     1
//    / \
//   2   3
//  /     \
// 4       5

// After mirror, print preorder traversal:
// Expected output?

medium

A. 1 2 3 4 5

B. 1 2 4 3 5

C. 1 3 2 5 4

D. 1 3 5 2 4

Solution

1. Step 1: Understand the mirror operation on the tree

   Swapping left and right children at every node flips the tree: Original root 1 has left=2, right=3 After mirror: left=3, right=2 Node 2 has left=4, right=NULL After mirror: left=NULL, right=4 Node 3 has left=NULL, right=5 After mirror: left=5, right=NULL

2. Step 2: Perform preorder traversal on mirrored tree

   Preorder: root, left, right Visit 1 Go left to 3 Go left to 5 (leaf) Back to 1, go right to 2 Go left NULL, go right 4 Sequence: 1 3 5 2 4

3. Final Answer:

   1 3 5 2 4 -> Option D

4. Quick Check:

   Mirror + 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 or postorder
• Missing leaf nodes in traversal

4. Identify the error in the following mirror function and select the fix:

void mirrorTree(struct Node* root) {
  if (root == NULL) return;
  mirrorTree(root->left);
  struct Node* temp = root->left;
  root->left = root->right;
  root->right = temp;
  mirrorTree(root->right);
}

medium

A. Add return type as int instead of void

B. Remove the base case check for NULL

C. Swap children before recursive calls to mirrorTree

D. Change temp to int instead of struct Node*

Solution

1. Step 1: Analyze the order of operations in the function

   The function calls mirrorTree on left and right children before swapping them. This causes the recursive calls to work on original children, not swapped ones.

2. Step 2: Correct the order to swap first, then recurse

   Swapping children first ensures recursive calls mirror the swapped subtrees correctly.

3. Final Answer:

   Swap children before recursive calls to mirrorTree -> Option C

4. Quick Check:

   Swap first, recurse later [OK]

Hint: Swap children before recursion to mirror correctly [OK]

Common Mistakes:

• Swapping after recursion causes incorrect mirror
• Removing base case causes crashes
• Changing temp type breaks pointer logic

5. Given a binary tree where some nodes have only one child, what is the effect of mirroring the tree on the structure and leaf nodes? Choose the correct statement.

hard

A. All leaf nodes remain leaf nodes but their positions are mirrored

B. Some leaf nodes become internal nodes after mirroring

C. The number of leaf nodes doubles after mirroring

D. Mirroring removes all nodes with only one child

Solution

1. Step 1: Understand mirroring effect on node positions

   Mirroring swaps left and right children but does not add or remove nodes. Leaf nodes remain leaf nodes but their positions flip left to right.

2. Step 2: Confirm leaf nodes count and structure

   Number of leaf nodes stays the same; no nodes become internal or are removed. Only their left-right positions change.

3. Final Answer:

   All leaf nodes remain leaf nodes but their positions are mirrored -> Option A

4. Quick Check:

   Mirror flips positions, leaf count unchanged [OK]

Hint: Mirror flips positions, leaf nodes stay leaf nodes [OK]

Common Mistakes:

• Thinking leaf nodes become internal nodes
• Assuming nodes are added or removed
• Believing leaf count changes