Mirror a Binary Tree in DSA C++ - Build from Scratch

Mirror a Binary Tree

📖 Scenario: You are working with a simple binary tree structure used in many applications like file systems or decision trees. Sometimes, you need to create a mirror image of this tree, flipping it left to right.

🎯 Goal: Build a program that creates a binary tree, then writes a function to mirror it by swapping left and right children at every node, and finally prints the mirrored tree in order.

📋 What You'll Learn

Create a binary tree with exactly 5 nodes with these values: 1 (root), 2 (left child of root), 3 (right child of root), 4 (left child of node 2), 5 (right child of node 2)

Create a function called mirror that takes a pointer to the root node and swaps its left and right children recursively

Create a function called inorder that prints the tree nodes in inorder traversal separated by spaces

Print the inorder traversal of the mirrored tree

💡 Why This Matters

🌍 Real World

Mirroring trees is useful in graphics, image processing, and reversing decision trees for analysis.

💼 Career

Understanding tree manipulations is important for software engineers working with data structures, algorithms, and system design.

1

Create the binary tree nodes

Create a struct called Node with an int data and two pointers left and right. Then create nodes with values 1, 2, 3, 4, and 5. Connect them to form this tree:
1 is root, 2 is left child of 1, 3 is right child of 1, 4 is left child of 2, 5 is right child of 2.

DSA C++

// Define struct Node and create nodes with values 1, 2, 3, 4, 5
// Connect nodes to form the tree
// Your code here

Hint

Define the Node struct with a constructor. Then create nodes and link them as described.

2

Create the mirror function

Create a function called mirror that takes a Node* called root. If root is not null, recursively call mirror on root->left and root->right, then swap root->left and root->right.

DSA C++

#include 
using namespace std;

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

// Define mirror function here
// Your code here

int main() {
    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);
    return 0;
}

Hint

Use recursion to visit left and right children, then swap them.

3

Create the inorder traversal function

Create a function called inorder that takes a Node* called root. If root is not null, recursively call inorder on root->left, then print root->data followed by a space, then recursively call inorder on root->right.

DSA C++

#include 
using namespace std;

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

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;
}

// Define inorder function here
// Your code here

int main() {
    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);
    return 0;
}

Hint

Use recursion to print left subtree, current node, then right subtree.

4

Mirror the tree and print inorder traversal

In main, call mirror(root) to mirror the tree, then call inorder(root) to print the mirrored tree nodes in inorder traversal.

DSA C++

#include 
using namespace std;

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

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;
}

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

int main() {
    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);
    // Call mirror and print inorder traversal
    // Your code here
    return 0;
}

Hint

Call mirror(root) first, then inorder(root) to print the mirrored tree.

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