Saturday, 27 May 2017

C++ Program to Check if two trees are Mirror


C++ Program to check if given two trees are mirror or not is given below along with its algorithm and output.

Asked in:  DE shaw, Amazon

Example of two mirror trees:

                5                                                   5                                 
              /    \                                               /   \
            /        \                                           /       \
          4          3                                       3         4
                    /    \                                   /   \
                  /        \                               /       \
                 1         2                           2          1

             (a)                                              (b)



         
                    
ALGORITHM

function CHECK(roota, rootb):
       IF  roota=NULL and rootb=NULL:
                   return true
       IF  roota=NULL or rootb=NULL:
                   return false
      return  (roota.data=rootb.data && CHECK(roota.left,rootb.right) &&
                                                             CHECK(roota.right,rootb.left))


PROGRAM:

#include <bits/stdc++.h>
using namespace std;


struct node
{
  int data;
  struct node *left,*right;
};

node *create_new_node(int data);
bool check_for_mirror(struct node *root1,struct node *root2);

int main()
{
      /*creating first binary tree*/

      node *root1=create_new_node(5);
      root1->left=create_new_node(3);
      root1->left->left=create_new_node(2);
      root1->left->right=create_new_node(1);
      root1->right=create_new_node(4);


      /*creating second binary tree*/


      node *root2=create_new_node(5);
      root2->left=create_new_node(4);
      root2->right=create_new_node(3);
      root2->right->left=create_new_node(1);
      root2->right->right=create_new_node(2);

      if(check_for_mirror(root1,root2))
      {
            printf("\n\nTrees are mirrors\n\n");
      }
      else
      {
            printf("\n\nTrees are not mirrors\n\n");
      }

      return 0;
}
node *create_new_node(int data)
{ 
       
       node *newnode=new node();
       newnode->data=data;
       newnode->left=newnode->right=NULL;
       return newnode;
}

bool check_for_mirror(struct node *root1,struct node *root2)
{
    if(root1==NULL && root2==NULL)
    {
         return true;
    }
    if(root1==NULL || root2==NULL)
    {
         return false;
    }

    return (root1->data==root2->data &&
             (check_for_mirror(root1->left,root2->right) &&
              check_for_mirror(root1->right,root2->left)));
}


OUTPUT


3 comments

how and when will the recursive call stop??

Consider the statement


consider the statement


root1==NULL || root2==NULL
(i.e either root1 is pointint to NULL
or root2 is pointint to NULL
which is not a condition of mirror tree
)

If this statemenet execute it will return false and
if the returned result is false then the
return statement will return false to its previous
invocation and this will be continue till the
result is returned to caller function because the
result of statement 2 of return statement must be
true for next invocation.

(It means recursive call is stopped)


Now consider this statement.


if root1==NULL && root2==NULL
(it means both are pointing to NULL
which should happen because left subtree of
tree 'a' and right subtree of tree'b' should
be end at simultaneouly and this will continue till
the second statement of return statement has no
further invocations.
)

If this statement executes then it will return true
and after that function will start popping out the
statement 3 of return statement which is pushed during
each invocations and start executing popped statement.
This will continue till the call stack becomes empty.

It means recursive calls will stop.




EmoticonEmoticon