Check if given two binary trees are the mirrors to each other

A mirror binary tree is a tree in which the left subtree is on the right side and right subtree on the left side. Let’s see below two binary trees for better understanding.

All left subtree moves to right and right subtree moves to left.

Here in the above images, both trees are mirrors to one another. The recursion formula is simple to this problem.

F(T1, T2) = (T1 == T2) & F(T1.left, T2.right) & F(T1.right, T2.left)
    = TRUE  // If both T1, T2 are NULL nodes.
    = FALSE // If one of them is NULL and other has data.

As we see in the recursive function, we compare one tree left sub-tree with another trees right subtree recursively. The code is as follows.

bool twoTreesMirrorsEach(struct Node *root1, struct Node *root2)
{
    if (root1 == NULL && root2 == NULL)
    {
        return true;
    }
    if (root1 == NULL || root2 == NULL)
    {
        return false;
    }
    return (root1->data == root2->data) &&
           twoTreesMirrorsEach(root1->left, root2->right) &&
           twoTreesMirrorsEach(root1->right, root2->left);
}

This code runs with a complexity O(N), where N is the number of nodes in the tree. Now, let us see the complete code with the main function.

// Output is 1 which is True.
1

This article is all about checking given two binary trees are mirrors to each other in a recursive way. If you have any better approach to solve this problem, please let our readers know by putting here below in comments. Happy Learning!.