Mirror a Binary Tree in DSA C++

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 every left and right child 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 begins the mirroring process

Step 2: Move to left child (originally right child) node 3, swap its children 6 and 7

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

Why: Mirror left subtree by swapping children of node 3

Step 3: Move to right child (originally left child) node 2, swap its children 4 and 5

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

Why: Mirror right subtree by swapping children of node 2

Step 4: Recursively apply the same swapping to leaf nodes 7, 6, 5, 4 which have no children

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

Why: Leaf nodes have no children, so no further swaps needed

Result:

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

This is the mirrored binary tree.

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

void mirrorTree(Node* root) {
    if (root == nullptr) return; // base case: empty node

    // swap left and right children
    Node* temp = root->left;
    root->left = root->right;
    root->right = temp;

    // recursively mirror left subtree
    mirrorTree(root->left);
    // recursively mirror right subtree
    mirrorTree(root->right);
}

void printInOrder(Node* root) {
    if (root == nullptr) return;
    printInOrder(root->left);
    cout << root->data << " ";
    printInOrder(root->right);
}

int main() {
    // Construct the tree from dry_run input
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);

    mirrorTree(root);

    printInOrder(root);
    cout << endl;
    return 0;
}

if (root == nullptr) return; // base case: empty node

stop recursion when node is empty

Node* temp = root->left; root->left = root->right; root->right = temp;

swap left and right children of current node

mirrorTree(root->left);

recursively mirror left subtree (which was originally right subtree)

mirrorTree(root->right);

recursively mirror right subtree (which was originally left subtree)

Output

7 3 6 1 5 2 4 

Complexity Analysis

Time: O(n) because we visit every node exactly once to swap children

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

vs Alternative: Iterative approaches exist but recursion is simpler and uses call stack; iterative may use explicit stack with similar time and space

Edge Cases

Empty tree (root is nullptr)

Function returns immediately without error

DSA C++

if (root == nullptr) return; // base case: empty node

Tree with only one node

No swaps happen, function returns after base case

DSA C++

if (root == nullptr) return; // base case: empty node

Tree with only left or only right children

Swapping still happens correctly, children pointers are swapped even if one is nullptr

DSA C++

Node* temp = root->left;
root->left = root->right;
root->right = temp;

When to Use This Pattern

When you need to transform a tree into its mirror image by swapping left and right children at every node, use the mirror tree pattern with recursion.

Common Mistakes

Mistake: Swapping children but forgetting to recursively mirror subtrees
Fix: Add recursive calls to mirror left and right subtrees after swapping

Mistake: Swapping children incorrectly by overwriting pointers without a temporary variable
Fix: Use a temporary variable to hold one child pointer during swap

Summary

It flips a binary tree by swapping every left and right child recursively.

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

The key insight is to swap children at each node and then mirror subtrees recursively.

Practice

1. What does mirroring a binary tree mean?

easy

A. Sorting the nodes in ascending order

B. Reversing the order of nodes in each level

C. Swapping the left and right children of every node

D. Deleting all leaf nodes

Solution

1. Step 1: Understand the mirror operation

   Mirroring means swapping left and right children of every node in the tree.

2. Step 2: Clarify what happens to nodes

   Each node's left child becomes its right child and vice versa, recursively.

3. Final Answer:

   Swapping the left and right children of every node -> Option C

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
• Confusing mirror with tree traversal order
• Assuming mirror deletes nodes

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

easy

A. void mirror(Node* root)

B. int mirror(Node root)

C. Node mirror(Node* root)

D. void mirror(Node root)

Solution

1. Step 1: Identify correct parameter type

   The function should take a pointer to the root node to modify the tree in place.

2. Step 2: Identify correct return type

   Since the tree is modified in place, the function can return void.

3. Final Answer:

   void mirror(Node* root) -> Option A

4. Quick Check:

   Pointer param + void return = void mirror(Node* root) [OK]

Hint: Use pointer parameter and void return for in-place tree changes [OK]

Common Mistakes:

• Passing node by value instead of pointer
• Returning Node instead of void
• Using incorrect parameter types

3. What is the output of the following code after mirroring the binary tree?

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

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

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

Node* root = new Node{1, new Node{2, new Node{4, nullptr, nullptr}, nullptr}, new Node{3, nullptr, new Node{5, nullptr, nullptr}}};
mirror(root);
// Print inorder traversal
void inorder(Node* node) {
  if (!node) return;
  inorder(node->left);
  std::cout << node->data << " ";
  inorder(node->right);
}
inorder(root);

medium

A. 5 3 1 4 2

B. 5 3 1 2 4

C. 1 2 4 3 5

D. 4 2 1 3 5

Solution

1. Step 1: Understand the original tree and inorder traversal

   Original inorder: left-root-right = 4 2 1 3 5

2. Step 2: Mirror swaps left and right children recursively

   Mirrored tree structure: 1 / \ 3 2 / \ 5 4 Inorder traversal now: 5 3 1 2 4

3. Final Answer:

   5 3 1 2 4 -> Option B

4. Quick Check:

   Inorder mirrored = 5 3 1 2 4 [OK]

Hint: Mirror swaps children; inorder reverses left-right order [OK]

Common Mistakes:

• Not swapping children correctly
• Confusing preorder with inorder traversal
• Printing original tree instead of mirrored

4. Identify the error in this mirror function and choose the fix:

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

medium

A. Swap root->left and root->right before recursive calls

B. Change 'if (root == nullptr)' to 'if (!root->left && !root->right)'

C. Add 'delete temp;' after swapping

D. Function should return void, remove 'return root;'

Solution

1. Step 1: Check function return type and usage

   The function is declared void but tries to return root pointer, which causes a compile error.

2. Step 2: Fix by removing the return statement

   Since the tree is modified in place, no return is needed; remove 'return root;'.

3. Final Answer:

   Function should return void, remove 'return root;' -> Option D

4. Quick Check:

   Void function must not return value [OK]

Hint: Void functions should not return values [OK]

Common Mistakes:

• Returning value from void function
• Changing base case incorrectly
• Deleting nodes unnecessarily

5. Given a binary tree, how would you modify the mirror function to also count how many nodes were swapped during the mirroring process?

hard

A. Return the number of nodes from the function and sum left and right counts

B. Add a counter parameter and increment it each time children are swapped

C. Use a global variable to count swaps inside the mirror function

D. Count nodes before and after mirroring and subtract counts

Solution

1. Step 1: Understand counting swaps during recursion

   Each node swap can be counted by returning 1 plus counts from left and right subtrees.

2. Step 2: Modify mirror to return int and sum counts

   Return 0 if node is null; else return 1 + mirror(left) + mirror(right).

3. Final Answer:

   Return the number of nodes from the function and sum left and right counts -> Option A

4. Quick Check:

   Return counts from recursion to sum swaps [OK]

Hint: Return counts from recursion to sum swapped nodes [OK]

Common Mistakes:

• Using global variables causing side effects
• Counting nodes before and after mirroring (no change)
• Not accumulating counts correctly