Mirror Reflection

Concepts Used

DFS , Recursion

Difficulty Level

Medium

Problem Statement :

Given two binary trees, we need to find whether one tree in the pair is the mirror image of another tree in the given pair.

See original problem statement here

Solution Approach :

Introduction :

Given two trees, they are mirror images of each other if the left value of one tree is equal to the right node value of another tree or vice-versa.

Method 1 (Stack):

We can use two stacks (stack1 & stack2) to traverse both the trees. Perform normal inorder traversal with stack1 and reverse inorder traversal with stack2, while traversing both the trees check if the values are similar, if at any point there is a different value then it is not a mirror tree.
>
NOTE: In Reverse Inorder Traversal, we will traverse right node first followed by root node then left node (which is opposite as Inorder Traversal).
>
See C++ implementation in data structures in c++.

Method 2 (Recursion) :

Given the root of two trees, n1 & n2, the trees are mirror image of each other if they follow following properties :

  • The root values of both trees should be equal.
  • The values of the left & right node should be equal i.e n1->left->value must be equal to n2->right->value, for all subtrees.

If both the trees follows above properties, they are mirror tree, otherwise not.

Solutions:

#include <stdio.h>

#include<stdlib.h>

#include <stdbool.h>



#define ll long long

#define REP(i, n) for (i = 0; i < n; i++)



struct nodelist

{

    ll value;

    struct nodelist *left;

    struct nodelist *right;

};

typedef struct nodelist node;

struct Queue

{

    int front, rear, size;

    unsigned capacity;

    node* *array;

};

typedef struct Queue queue;



queue* createQueue(unsigned capacity)

{

    queue* qu =(queue*)malloc(sizeof(queue));

    qu->capacity = capacity;

    qu->front = qu->size =0;

    qu->rear = capacity-1;

    qu->array = (node **)malloc(qu->capacity * sizeof(node));

    return qu;

}



int isFull(queue*  queue1)

{

    return (queue1->size == queue1->capacity);

}

int isEmpty(queue* queue1)

{

    return (queue1->size==0);

}



void enqueue(queue* queue1, node* item)

{

    if(isFull(queue1))

        return ;

    queue1->rear = (queue1->rear +1 )%queue1->capacity;

    queue1->array[queue1->rear] = item;

    queue1->size = queue1->size +1;



}



node dequeue(queue* queue1)

{

    node* item = queue1->array[queue1->front];

    queue1->front = (queue1->front +1)%queue1->capacity;

    queue1->size = queue1->size -1;

    return *item;

}



node* front(queue* queue1)

{

    return queue1->array[queue1->front];

}



node* rear(queue * queue1)

{

    return queue1->array[queue1->rear];

}

node *createNode(ll value)

{

    node *t= (node *) malloc(sizeof(node));

    t->value = value;

    t->right = t->left = NULL;

    return  t;

}

void deleteNode(node*t)

{

    free(t);

}

node *replaceNegativeOne(node *root)

{

    if(root==NULL ||(root->value == -1 && root->left == NULL && root->right == NULL))

        return NULL;

    root->left = replaceNegativeOne(root->left);

    root->right = replaceNegativeOne(root->right);

    return root;

}



void deleteTree(node *node1)

{

    if(node1==NULL)

        return;

    deleteTree(node1->left);

    deleteTree(node1->right);

    free(node1);

}

node *createTreeByLevelTree()

{

    ll n,m;

    queue* queue1 = createQueue(100000);

    node *root, *t;

    root = NULL;

    while(scanf("%lld", &n))

    {

        if(isEmpty(queue1))

        {

            root= createNode(n);

            enqueue(queue1,root);

            continue;

        }

        scanf("%lld", &m);

        t = front(queue1);

        dequeue(queue1);

        t->left =createNode(n);

        t->right=createNode(m);

        if(t->left->value !=-1)

            enqueue(queue1,t->left);

        if(t->right->value !=-1)

            enqueue(queue1,t->right);

        if(isEmpty(queue1))

            break;

    }

    return root;

}

bool checkMirrorTree(node* a, node* b)

{

    if(a==NULL && b==NULL)

     return 1;



    if(a->value != b->value)

     return 0;



    return checkMirrorTree(a->left,b->right) && checkMirrorTree(a->right,b->left);

}




int main() {



    node *root = NULL;

    root = createTreeByLevelTree();

    root = replaceNegativeOne(root);

    node *root2 = NULL;

    root2 = createTreeByLevelTree();

    root2 = replaceNegativeOne(root2);

    if(checkMirrorTree(root,root2))

        printf("true\n");

    else

        printf("false\n");

    deleteTree(root);

    return 0;

}
#define REP(i, n) for (i = 0; i < n; i++)

#define pb(a) push_back(a)

#define vi vector<long>

#define ll long long

#include <bits/stdc++.h>

using namespace std;

struct node

{

    ll value;

    node *left;

    node *right;

};



node *createNode(ll value)

{

    node *t = new node();

    t->value = value;

    t->right = t->left = NULL;

    return t;

}



void deleteNode(node *t)

{

    delete t;

}





node *replaceNegativeOne(node *root)

{

    if (root == NULL || (root->value == -1 && root->left == NULL && root->right == NULL))

        return NULL;

    root->left = replaceNegativeOne(root->left);

    root->right = replaceNegativeOne(root->right);

    return root;

}



node *createTreeByLevelTree()

{

    ll n, m;

    queue<node *> q;



    node *root, *t;



    root = NULL;



    while (cin >> n)

    {

        if (q.empty())

        {

            root = createNode(n);

            q.push(root);

            continue;

        }

        cin >> m;



        t = q.front();

        q.pop();



        t->left = createNode(n);

        t->right = createNode(m);



        if (t->left->value != -1)

        {

            q.push(t->left);

        }



        if (t->right->value != -1)

        {

            q.push(t->right);

        }

         if (q.empty())

        {

            break;

        }

    }



    return root;

}



void deleteTree(node *node)

{

    if (node == NULL)

        return;



    deleteTree(node->left);

    deleteTree(node->right);

    delete node;

}

bool checkMirrorTree(node* root1, node* root2)

{

     stack<node*> st1, st2; 

    while (1) 

    { 

        while (root1 && root2) 

        { 



            if (root1->value != root2->value) 

                return 0; 



            st1.push(root1); 

            st2.push(root2); 

            root1 = root1->left; 

            root2 = root2->right;     

        } 



        if (!(root1 == NULL && root2 == NULL)) 

            return 0; 



        if (!st1.empty() && !st2.empty()) 

        { 

            root1 = st1.top(); 

            root2 = st2.top(); 

            st1.pop();  

            st2.pop(); 



            root1 = root1->right; 



            root2 = root2->left; 

        }     



        else

            break; 

    } 



    return 1; 
}




int main()

{

    node *root = NULL;

    root = createTreeByLevelTree();

    root = replaceNegativeOne(root);

    node *root2 = NULL;

    root2 = createTreeByLevelTree();

    root2 = replaceNegativeOne(root2);



    if(checkMirrorTree(root,root2))

        cout<<"true"<<endl;

    else

        cout<<"false"<<endl;

    deleteTree(root);

    return 0;

}
import java.util.LinkedList;

import java.util.*;

import java.util.Scanner;

import java.io.*;



class Node

{

    long value;

    Node left, right;



    public Node(long item)

    {

        value = item;

        left = right = null;

    }

}

class BinaryTree {

    Node root;



    BinaryTree() {

        root = null;

    }



    Node createNode(long value) {

        Node t = new Node(value);

        return t;

    }



    Node replaceNegativeOne(Node root) {

        if (root == null || (root.value == -1 && root.left == null && root.right == null)) {

            return null;

        }

        root.left = replaceNegativeOne(root.left);

        root.right = replaceNegativeOne(root.right);

        return root;

    }



    Node createTreeByLevelTree(Scanner sc) {



        long n, m;

        Queue<Node> queue = new LinkedList<>();

        Node t;

        root = null;

        while (sc.hasNext()) {

            n = sc.nextLong();

            if (queue.isEmpty()) {

                root = createNode(n);

                ((LinkedList<Node>) queue).add(root);

                continue;

            }

            m = sc.nextLong();

            t = ((LinkedList<Node>) queue).peekFirst();

            ((LinkedList<Node>) queue).pop();

            t.left = createNode(n);

            t.right = createNode(m);

            if (t.left.value != -1)

                ((LinkedList<Node>) queue).add(t.left);

            if (t.right.value != -1)

                ((LinkedList<Node>) queue).add(t.right);

            if (queue.isEmpty())

                break;

        }

        return root;

    }



    void deleteTree(Node node) {

        node = null;

    }

boolean checkMirrorTree(Node node1, Node node2) {

    if(node1 ==null  && node2==null)

     return true;



    if(node1.value != node2.value)

     return false;



    return checkMirrorTree(node1.left,node2.right) && checkMirrorTree(node1.right,node2.left);

}




}

public class Main {



    public static void main(String[] args) {

        // write your code here

        Scanner sc = new Scanner(System.in);

        BinaryTree bt = new BinaryTree();

        bt.root = bt.createTreeByLevelTree(sc);

        bt.root = bt.replaceNegativeOne(bt.root);

        BinaryTree bt1 = new BinaryTree();

        bt1.root = bt1.createTreeByLevelTree(sc);

        bt1.root = bt1.replaceNegativeOne(bt1.root);

        if(bt.checkMirrorTree(bt.root, bt1.root))

            System.out.println("true");

        else

            System.out.println("false");

        bt.deleteTree(bt.root);

    }

}

Previous post Maximum Turns
Next post Size of Tree

Leave a Reply

Your email address will not be published. Required fields are marked *