DSA Series Chapter 25 – MIRROR OF BINARY TREE (C VERSION)

on

 


[JOIN OUR BLOG] for daily coding insights

DSA Series Chapter 25  – MIRROR OF BINARY TREE (C VERSION)

1. Objective

    To convert a given binary tree into its mirror image by recursively swapping the left and right subtrees of every node using C.

2. Definition (Exam-Ready)

The mirror of a binary tree is a tree in which the left and right children of all nodes are interchanged.

3. Example

Original Binary Tree

            1
          /   \
         2     3
        / \
       4   5

Mirror Binary Tree

            1
          /   \
         3     2
              / \
             5   4

4. Key Observation

  • Mirroring is a structural transformation

  • Data values remain unchanged

  • Only links (pointers) are swapped

5. Core Logic (Recursive)

For each node:

  1. Swap left and right children

  2. Recursively mirror left subtree

  3. Recursively mirror right subtree

6. Recursive Formula

mirror(node) =
    return                          if node == NULL
    swap(node->left, node->right)
    mirror(node->left)
    mirror(node->right)

7. Structure Definition

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

8. Function to Mirror Binary Tree

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

9. Line-by-Line Explanation

if (root == NULL)
    return;

  • Base case

  • Empty subtree needs no mirroring

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

  • Swaps left and right child pointers

mirrorTree(root->left);
mirrorTree(root->right);

  • Recursively mirrors subtrees

10. Complete C Program

#include <stdio.h>
#include <stdlib.h>
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
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);
}
void inorder(struct Node* root) {
    if (root == NULL)
        return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}
int main() {
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    printf("Inorder traversal before mirroring: ");
    inorder(root);
    mirrorTree(root);
    printf("\nInorder traversal after mirroring: ");
    inorder(root);
    return 0;
}

11. Output

Inorder traversal before mirroring: 4 2 5 1 3
Inorder traversal after mirroring: 3 1 5 2 4

12. Time and Space Complexity

Time Complexity

  • O(n)
    Each node is visited once.

Space Complexity

  • O(h) due to recursion stack.

13. Important Exam Points

  • Mirror operation changes structure, not data

  • Recursive solution is preferred

  • Inorder traversal changes after mirroring

  • Preorder root remains same

14. Common Beginner Mistakes

  • Forgetting base case

  • Swapping data instead of pointers

  • Calling recursion before swap

  • Assuming mirror only affects leaf nodes

15. Learning Outcome

After completing this post, learners can:

  • Understand mirror concept clearly

  • Implement mirror operation in C

  • Visualize structural transformations

  • Answer exam/interview questions confidently

ALSO CHECK 

DS(Data Structure) Python&C Edition

DSA Series Chapter 1 Time & Space Complexity ( C Edition)

DSA Series Chapter 2 Arrays  (C Version)


DSA Series Chapter 2 Arrays  (Python Version)

DSA Series Chapter 3 Strings (C Version)


DSA Series Chapter 3 Strings (Python Version)


DSA Series Chapter 4 Linked Lists (Python Version)


DSA Series Chapter 4 Linked Lists (C Version)


DSA Series Chapter 5 Stacks (Python Version)


DSA Series Chapter 5  Stacks  (C Version)




















DSA Series Chapter 13 - Binary Tree traversal, BFS, DFT/DFS, Preorder Traversal In Binary Tree


DSA Series Chapter 14 - InOrder Traversal (Binary Tree C Version)


DSA Series Chapter 14 - InOrder Traversal (Binary Tree Python Version)

 

DSA Series Chapter 15 – POSTORDER TRAVERSAL (BINARY TREE)(Python Version)


DSA Series Chapter 15 – POSTORDER TRAVERSAL (BINARY TREE)(C Version)


DSA Series Chapter 16 – LEVEL ORDER TRAVERSAL(BINARY TREE BFS)(C Version)


DSA Series Chapter 16 – LEVEL ORDER TRAVERSAL(BINARY TREE BFS)(Python Version)



DSA Series Chapter 19 : DELETION IN BINARY TREE(C Version)

DSA Series Chapter 19 : DELETION IN BINARY TREE(Python Version)


DSA Series Chapter 20 – HEIGHT OF BINARY TREE(C Version)

DSA Series Chapter 20 – HEIGHT OF BINARY TREE(Python Version)






Tail Recursion Optimization: How Compilers Convert Recursion Into Iteration


Advanced Recursion: Memoization vs. Tabulation — The Deep Optimization Blueprint for Professionals


Advanced Sorting Algorithms: Merge Sort Internals — Merge Tree, Cache Behavior & Real Cost Analysis


Enjoyed this post? [Follow here] for daily coding insights

Comments

Post a Comment