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,

The steps are as follows:

1. For every sub-tree starting from the root node:
2. Swap Left and Right sub-trees.

The pseudocode is as follows:

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.

The steps are as follows:

1. Do a level order traversal and swap every left and right child
2. Define a Queue
3. Insert root into Queue
4. If queue is not empty
   5. Deque node from Queue
   6. Swap left and right child of node of step 5.
   7. Push left and right child into queue.
   8. Go to step 4.

The pseudocode is as follows:

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

Space and Time complexity analysis

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.