Convert a binary tree into its mirror tree

Get FREE domain for 1st year and build your brand new site

Problem Statement

Given a binary tree, we have to write an algoritm to convert the binary tree to its mirror tree. A mirror tree is another binary tree with left and right children of all non-leaf nodes interchanged. The following image shows an example of a binary tree and the corressponding mirror tree.

As you can see, the binary tree has been mirrored along its root and the left children are now the right children in the mirror tree and vice-versa.

Idea behind solving this problem

We have solved this using two techniques:

• Recursive approach
• Iterative approach (using queues)

1. Recursive approach

The first method to solve this problem would be to use the power of recursion. We need to create a helper function that mirrors the tree recursively. Lets call the function mirror().

After the tree has been mirrored, the tree is traversed in an inorder fashion meaning the right subtree is traversed followed by the root and the right subtree is traversed at the last.

This will help to see the mirror image as the elements in right subtree will come before the root after the mirrot (the inorder traversal keeps the root at the center so it will be easy to distiguish and check). The algorithm to solve this problem is,

Call Mirror for left-subtree    i.e., Mirror(left-subtree)
Call Mirror for right-subtree  i.e., Mirror(right-subtree)
Swap left and right subtrees.
temp = left-subtree
left-subtree = right-subtree
right-subtree = temp


2. Iterative approach (using queues)

This method requires the use of queue based level order traversal. While doing the traversal, swap the left and right children of every node. The idea is to use a queue to store the nodes and swap them each time and push back the swapped places in the queue. This will require to use the same mirror function as before but this time we will be using queue to solve it. The algorithm to solve this is mentioned below.

Initialize queue Q
Enqueue the root
while Q is not empty, do
current-node = Q.front()
Dequeue the node
swap current-node.left and current-node.right
push back the left and right child into the queue


Once this is completed, just simply traverse the tree using the inorder traversal and the tree will be mirrored.

Let us see this in a small example. Consider the following tree.

         3
/   \
5       1
/ \     / \
6   2   0   8

• Here root is 3. Enqueue it. Queue contains: [3]
• Initialize current-node to queue-front. current-node: 3
• Dequeue. Queue contains: []
• Swap current-node-left and current-node-right. Now the tree looks like this:
         3
/   \
1       5
/ \     / \
6   2   0   8


Add current-node-left and current-node-right to the queue. Queue contains: [5, 1]
Dequeue. Queue contains: [5], current-node = 1
Swap current-node-left and current-node-right. Now the tree looks like this:

         3
/   \
1       5
/ \     / \
2   6   0   8


Dequeue again until queue is empty. Queue now contains: [], current-node = 5
Swap current-node-left and current-node-right. Now the tree looks like this:

         3
/   \
1       5
/ \     / \
2   6   8   0


Hence, the mirror queue is done.

Code implementation

Below is the code implementation of both the solutions: using recursion as well as using queue. The language of preference is C++. I have also created a Github repository that has the presented solution here as well as a solution in Python. You can visit this link if you wish to see the repository.

1. Recursive approach

#include <iostream>
using namespace std;

/* A binary tree node has data, pointer
to left child and a pointer to right child */
struct Node
{
int data;
struct Node* left;
struct Node* right;
};

/* Helper function that allocates a new node with
the given data and NULL left and right pointers. */
struct Node* newNode(int data)
{
struct Node* node = (struct Node*)
malloc(sizeof(struct Node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

void mirror(struct Node* node)
{
if (node == NULL)
return;
else
{
struct Node* temp;

/* do the subtrees */
mirror(node->left);
mirror(node->right);

/* swap the pointers in this node */
temp	 = node->left;
node->left = node->right;
node->right = temp;
}
}

/* Helper function to print
Inorder traversal.*/
void inOrder(struct Node* node)
{
if (node == NULL)
return;

inOrder(node->left);
cout << node->data << " ";
inOrder(node->right);
}

// Driver Code
int main()
{
struct Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);

/* Print inorder traversal of the input tree */
cout << "Inorder traversal of the constructed tree \n"
inOrder(root);

/* Convert tree to its mirror */
mirror(root);

/* Print inorder traversal of the mirror tree */
cout << "\nInorder traversal of the mirror tree is \n";
inOrder(root);

return 0;
}


2. Iterative approach

#include <iostream>
#include <queue>
using namespace std;

/* A binary tree node has data, pointer to
left child and a pointer to right child */
struct Node
{
int data;
struct Node* left;
struct Node* right;
};

/* Helper function that allocates a new node
with the given data and NULL left and right
pointers. */
struct Node* newNode(int data)

{
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return(node);
}

void mirror(Node* root)
{
if (root == NULL)
return;

queue<Node*> q;
q.push(root);

// Do BFS. While doing BFS, keep swapping
// left and right children
while (!q.empty())
{
// pop top node from queue
Node* curr = q.front();
q.pop();

// swap left child with right child
swap(curr->left, curr->right);

// push left and right children
if (curr->left)
q.push(curr->left);
if (curr->right)
q.push(curr->right);
}
}

/* Helper function to print Inorder traversal.*/
void inOrder(struct Node* node)
{
if (node == NULL)
return;
inOrder(node->left);
cout << node->data << " ";
inOrder(node->right);
}

/* Driver program to test mirror() */
int main()
{
struct Node *root = newNode(1);
root->left	 = newNode(2);
root->right	 = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);

/* Print inorder traversal of the input tree */
cout << "\n Inorder traversal of the original tree \n";
inOrder(root);

/* Convert tree to its mirror */
mirror(root);

/* Print inorder traversal of the mirror tree */
cout << "\n Inorder traversal of the mirror \n";
inOrder(root);

return 0;
}


1. Recusrive approach

Time Complexity: O(n). Since the solution is using recusrsive approach along with just manipulating the pointers (which are constant time operations thus having a time complexity of O(1)), the time complexity of this approach will be the same as the level order traversal. And the traversal being used is inorder traversal, which has a time complexity of O(n).

Case: Skewed tree (One of the subtrees is empty and other subtree is non-empty)

Recursive function for this case will be,

T(n) = T(k) + T(n – k – 1) + c

k is 0 in this case.
T(n) = T(0) + T(n-1) + c
T(n) = 2T(0) + T(n-2) + 2c
T(n) = 3T(0) + T(n-3) + 3c
T(n) = 4T(0) + T(n-4) + 4c

…………………………………………
T(n) = (n-1)T(0) + T(1) + (n-1)c
T(n) = nT(0) + (n)c

Value of T(0) will be some constant say d. (traversing a empty tree will take some constants time)

T(n) = n(c+d)
T(n) = Θ(n) (Theta of n)

Space Complexity: O(n) if we consider size of stack for function calls, otherwise then O(1). The recursive approach does not use any other space other than the space for the stack calls.

2. Iterative approach

Time Complexity: O(n) where n is number of nodes in the binary tree
Space Complexity: O(n) where n is number of nodes in the binary tree (we use to store the child nodes for the specific node.