Given a binary tree, we aim to find its mirror tree.
A Mirror tree is a binary tree where it’s left and right subtrees are swaps its positions. A recursive definition of the mirror tree is a binary tree T(P, L, R) is T(P, T(R), T(L)). Here both L(left) and R(right) subtrees swapped their position in the mirror tree. T(R) is a mirror tree of right subtree, T(L) is a mirror tree of the left subtree.
// Forumla
[latex display="true"]M(P, L, R) = T(P, M(R), M(L))[/latex]
// Where P(parent) is not NULL.
// Here
M --> is Mirror tree
P --> Parent node.
L --> Left subtree.
R --> Right subtree.
Let’s check below example binary tree and its mirror tree. A mirror of a mirrored binary tree forms its original tree.
Finally, let’s see the code snippet for this solution
// Mirror of a binary tree
void mirror(struct Node *root)
{
if(root == NULL)
return;
mirror(root->left);
mirror(root->right);
// Swap left and right subtrees
struct Node *tmp = root->left;
root->left = root->right;
root->right = tmp;
}
As it is doing in post-order traversal, the complexity for this solution is . The complete code for this solution is as follows.
// Output
Tree in-order:
5 12 24 14 7 9
Mirror of tree:
9 7 14 24 12 5
Complexity:
Mirror of a binary tree is as described above. If you know any better solution or found any errors in the above code, please let readers know by commenting here below. Cheers!.