Namanjeet Singh

Mirror Tree Problem – Convert Binary tree to Mirror 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 of mirror tree

Example Explanation

mirror tree example

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:

Inorder traversal of original tree is
4 2 5 1 6 3 7 
Inorder traversal of the mirrored tree is 
7 3 6 1 5 2 4 

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

Constraints of Mirror tree

1<=N<=3000
109<=Data<=109

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)Call the mirror function for the right sub-tree, i.e. Mirror(right sub-tree)Swap left and right sub-trees using,
      • temp = left sub-treeleft sub-tree = right sub-treeright 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++:

Implementation of Mirror Tree
#include<bits/stdc++.h>
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;
};

/* 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;

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

        // swapping the pointers for this node
        temp = node->left;
        node->left = node->right;
        node->right = temp;
    }
}

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

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


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

    // inorder traversal of the original tree 
    cout << "Inorder traversal of original tree is" << endl;
    inorder(root);

    // mirror the tree
    mirror(root);

    // inorder traversal of the mirrored tree
    cout << "\nInorder traversal of the mirrored tree is \n";
    inorder(root);

    return 0;
}

Output

Inorder traversal of original tree is
4 2 5 1 6 3 7 
Inorder traversal of the mirrored tree is 
7 3 6 1 5 2 4 

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

import java.util.*;

class Main {

// a binary tree node has data, pointer to
// left child and a pointer to right child
static class Node {
    int data;
    Node left;
    Node right;
}

// function that allocates
// a new node with the given data and null left and right pointers
static Node newNode(int data) {
    Node newNode = new Node();
    newNode.data = data;
    newNode.left = null;
    newNode.right = null;
    return newNode;
}

// function to print Inorder traversal
static void inorder(Node root) {
    if (root == null)
        return;
    inorder(root.left);
    System.out.print(root.data + " ");
    inorder(root.right);
}


static Node mirror(Node root) {
    if (root == null) {
        return null;

    }
    // mirror the subtrees
    Node mirror = newNode(root.data);
    mirror.right = mirror(root.left);
    mirror.left = mirror(root.right);
    return mirror;
}

public static void main(String args[]) {

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

    //  inorder traversal of the input tree
    System.out.print("Inorder traversal of original tree is \n");
    inorder(root);

    Node mirror = null;
    mirror = mirror(root);

    // inorder traversal of the mirrored tree
    System.out.print("\nInorder traversal of the mirrored tree is \n");
    inorder(mirror);
    }
}

Output

Inorder traversal of original tree is
4 2 5 1 6 3 7 
Inorder traversal of the mirrored tree is 
7 3 6 1 5 2 4 

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

# function to create a new tree node
class newNode:
    def __init__(self,data):
        self.data = data
        self.left = self.right = None

def mirror(node):

    if (node == None):
        return
    else:
        temp = node

        # mirror the subtrees
        mirror(node.left)
        mirror(node.right)

        # swapping the pointers for this node
        temp = node.left
        node.left = node.right
        node.right = temp

# function to print Inorder traversal
def inorder(node) :

    if (node == None):
        return

    inorder(node.left)
    print(node.data, end = " ")
    inorder(node.right)


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)

# inorder traversal of the original tree
print("Inorder traversal of original tree is")
inorder(root)

# mirror the tree
mirror(root)

# inorder traversal of the mirrored tree
print("\nInorder traversal of the mirrored tree is")
inorder(root)

Output

Inorder traversal of original tree is
4 2 5 1 6 3 7 
Inorder traversal of the mirrored tree is 
7 3 6 1 5 2 4 

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++:

  • Let us now see the implementation of the Mirror for the following binary tree in C++:
Implementation of Mirror for Binary Tree
#include<bits/stdc++.h>
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;
};

/* 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);

    // while implementing level order traversal, 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);
    }
}


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

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

    // inorder traversal of the original tree 
    cout << "Inorder traversal of original tree is" << endl;
    inorder(root);

    // mirror the tree
    mirror(root);

    // inorder traversal of the mirrored tree
    cout << "\nInorder traversal of the mirrored tree is \n";
    inorder(root);

    return 0;
}

Output

Inorder traversal of original tree is
4 2 5 1 6 3 7 
Inorder traversal of the mirrored tree is 
7 3 6 1 5 2 4 

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

import java.util.*;
class Main {

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

/* function that allocates a new node
with the given data and null left and right pointers */
static Node newNode(int data) {
    Node node = new Node();
    node.data = data;
    node.left = node.right = null;
    return(node);
}

static void mirror(Node root)
{
    if (root == null)
        return;

    Queue<Node> q = new LinkedList<>();
    q.add(root);

    // while implementing level order traversal, keep swapping
    // left and right children
    while (q.size() > 0) {
        // pop top node from queue
        Node curr = q.peek();
        q.remove();

        // swap left child with right child
        Node temp = curr.left;
        curr.left = curr.right;
        curr.right = temp;

        // push left and right children
        if (curr.left != null)
            q.add(curr.left);
        if (curr.right != null)
            q.add(curr.right);
    }
}

// function to print Inorder traversal
static void inorder( Node node)
{
    if (node == null)
        return;
    inorder(node.left);
    System.out.print( node.data + " ");
    inorder(node.right);
}


public static void main(String args[]) {

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

    // inorder traversal of the original tree 
    System.out.print("Inorder traversal of original tree is \n");
    inorder(root);

    // mirror the tree
    mirror(root);

    // inorder traversal of the mirrored tree
    System.out.print("\nInorder traversal of the mirrored tree is \n");
    inorder(root);
    }
}

Output

Inorder traversal of original tree is
4 2 5 1 6 3 7 
Inorder traversal of the mirrored tree is 
7 3 6 1 5 2 4 

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

# function to create a new tree node
class newNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def mirror( root):

    if (root == None):
        return

    q = []
    q.append(root)

    # while implmementing level order traversal, keep swapping
    # left and right children
    while (len(q)):

        # pop top node from queue
        curr = q[0]
        q.pop(0)

        # swap left child with right child
        curr.left, curr.right = curr.right, curr.left

        # append left and right children
        if (curr.left):
            q.append(curr.left)
        if (curr.right):
            q.append(curr.right)

# function to print Inorder traversal 
def inorder( node):
    if (node == None):
        return
    inorder(node.left)
    print(node.data, end = " ")
    inorder(node.right)

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)

# inorder traversal of the original tree
print("Inorder traversal of original tree is")
inorder(root)

# mirror the tree
mirror(root)

# inorder traversal of the mirrored tree
print("\nInorder traversal of the mirrored tree is")
inorder(root)

Output

Inorder traversal of original tree is
4 2 5 1 6 3 7 
Inorder traversal of the mirrored tree is 
7 3 6 1 5 2 4 

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).

Conclusion

  • A mirror tree is a form of the binary tree where left and right children of all non-leaf nodes are interchanged.
  • Complexities for Recursive approach
    • Time Complexity – O(n)
    • Space Complexity – O(n)
  • Complexities for Iterative approach using Queue data structure
    • Time Complexity – O(n)
    • Space Complexity – O(n)

Author