Mirror binary tree

Mirror binary trees are one of the important concepts in data structures that offer insights into tree transformations and symmetry. So, In this blog, we will dive into the mirror binary trees concept, exploring their definition, construction, and real-life applications.

What is Mirror binary Tree?

A mirror binary tree is a binary tree where the left and right child nodes of each parent node are swapped or interchanged with each other.
So, we can also say that this tree is also famous as a flipped or invert binary tree.
In the mirror tree, each node’s left child becomes its right child, and its right child node becomes its left child. So, the flipping or inversion approach is applied recursively to all nodes in the tree to form a mirror image of a binary tree.

Code :

#include <iostream>

// Definition of binary tree node
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int value) : data(value), left(nullptr), right(nullptr) {}
};

// Function to invert (mirror) a binary tree recursively
Node* invertBinaryTree(Node* root) {
    if (root == nullptr) {
        return nullptr;
    }

    // Recursively invert the left and right subtrees
    Node* left = invertBinaryTree(root->left);
    Node* right = invertBinaryTree(root->right);

    // Swap the left and right subtrees
    root->left = right;
    root->right = left;

    return root;
}

// Function to perform inorder traversal of a binary tree
void inorderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }
    inorderTraversal(root->left);
    std::cout << root->data << " ";
    inorderTraversal(root->right);
}

int main() {
    // Creating a binary tree manually
    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);

    // Print the original binary tree
    std::cout << "Original Binary Tree (Inorder Traversal): ";
    inorderTraversal(root);
    std::cout << std::endl;

    // Invert the binary tree
    Node* invertedRoot = invertBinaryTree(root);

    // Print the inverted binary tree
    std::cout << "Inverted Binary Tree (Inorder Traversal): ";
    inorderTraversal(invertedRoot);
    std::cout << std::endl;

    return 0;
}

Code Explanation of Mirror Binary Tree Problem:

Now, let’s undertsand the above code:

1. Firstly, we begin by including the necessary header file.
2. Next, we define a Node struct representing a node in the binary tree. It has three members: data to store the node’s value, and left and right pointers for the left and right child nodes, respectively.
3. Now, we will make the invertBinaryTree function that takes a Node pointer as the root variable and recursively inverts it into the binary tree.
   • First, it checks if the current node (root) is nullptr or not. If it is, then returns nullptr as output that indicates that we will reach the end of the subtree.
   • If the node value is not equal to nullptr, then recursively calls the invertBinaryTree function for the left and right subtrees.
   • Next, it swaps the left and right child pointers value of the current node (root) to invert the positions of the subtrees.
   • Finally, it will return the root node after the inversion process.
4. Then by using the inorderTraversal function, we will perform an inorder traversal of the binary tree and prints the node values.
5. In the main function, we manually create a binary tree and then print the original binary tree using the inorderTraversal function. Next, we print the inverted binary tree.

What is the use of the concept of a mirror binary tree?

So, mirror, a binary tree is often used in various tree-based algorithms and problems, such as:

1. In determining if two binary trees are mirrors of each other or not.
2. Used while performing operations that require reversing or interchanging the left and right children of nodes.

Conclusion:

In conclusion, a mirror binary tree is a binary tree where the left and right children of each node are swapped, resulting in a flipped or inverted version of the original tree.
It is very important to note that mirror binary trees may not be suitable for all scenarios. For large trees or complex operations, alternative data structures and algorithms might be more appropriate for these types of scenarios.