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.