Convert Mirror Tree to Binary Tree

Problem Statement

Given a binary tree, our task is to convert this binary tree into its mirror tree. A mirror tree is another form of a binary tree where the left and right children of all non-leaf nodes are interchanged.

Example of Mirror Tree

Let us try to mirror the following binary tree:

Example Explanation

In the above-shown example consider the dotted line as a mirror thus the tree on the left side is the original binary tree while tree on the right is the mirrored binary tree.

Input/ Output of Mirror Tree

The input statement contains each tree node's data separated by a single space in a single line. If any node in the binary tree is NULL, we will put -1 in its place. Therefore, for the tree depicted in the above example the input will be given as:

1 2 3 4 5 6 7 -1 -1 -1 -1 -1 -1 -1 -1

The output for the above given input will the following:

Here, output includes the Inorder traversal for both the original and mirrored tree.

Constraints of Mirror tree

$1 <= N <= 3000$ $-10^{9} <= Data <= 10^{9}$

Here N is the number of nodes in the tree, and Data denotes the value contained in the node of the binary tree.

Approach 1- Recursive

The intuition of this approach is to solve the problem using recursion. We will create a mirror() function that will recursively mirror the left and right sub-tree.

• Algorithm

  The algorithm for this approach is as follows:

  1. Call the mirror function for the left sub-tree, i.e. Mirror(left sub-tree)
  2. Call the mirror function for the right sub-tree, i.e. Mirror(right sub-tree)
  3. Swap left and right sub-trees using,
     • temp = left sub-tree
     • left sub-tree = right sub-tree
     • right sub-tree = temp

  After the tree is mirrored, we will traverse it using the Inorder traversal, meaning the left sub-tree is traversed first, followed by the root node and the right sub-tree at the last.

• Implementation

  Let us now see the implementation of the Mirror for the following binary tree in C++:

Output

Let us now see the implementation of the Mirror binary tree in Java:

Output

Let us now see the implementation of the Mirror binary tree in Python

Output

• Time Complexity

  In the above code implementation, we are using the recursive approach along with updating the pointers at every recursive call (that are constant time operations thus having a time complexity of $O(1)$), therefore, the time complexity of this approach will be the same as that of the inorder traversal, which is $O(n)$.

• Space Complexity

  If we consider the size of the stack for function calls, the space complexity of the above implemented recursive approach is $O(n)$. The recursive approach does not utilise any other auxiliary space other than the space used for the stack calls.

Approach 2- Iterative method using Queues

The intuition of this approach is to implement level order traversal using the queue data structure. While doing traversal, swap left and right children of every node.

• Algorithm

  The algorithm for this approach is as follows:

  1. Perform a level order traversal, swapping every left and right child
  2. Create a queue and add the root node to it.
  3. If the queue is not empty,
     • deque node from the queue
     • swap left and right children of the removed node
     • push back the left and right child of the removed node to the queue
     • return to step 3

• Implementation

  Let us now see the implementation of the Mirror for the following binary tree in C++:

Output

Let us now see the implementation of the Mirror binary tree in Java:

Output

Let us now see the implementation of the Mirror binary tree in Python:

Output

• Time Complexity

  We implement level order traversal, which has a time complexity of $O(n)$, as well as the swapping of left and right children, which has a constant time complexity, for a total time complexity of $O(n)$.

• Space Complexity

  Because this approach employs the queue data structure, the space complexity of this method is $O(n)$.