CareerCup

store the two traversal (inorder,preorder) of left and right subtree in the disk


start building smaller(size suitable for memory load) tree starting from leaves nodes by the help of left and right traversal

if they are mirror image of each other then do same for rest of the tree (u can discard these smaller tree,since they are already mirror image)

and at any point of time if they are not mirror image then u can return false

If tree is huge, probably it will be containing huge satellite data(usually a structure). we can represent the tree by an array whose elements are the pointers to the data of the node, such that, the root resides at index 0 and for a given ith node, its left child stays at (2i+1) and right child stays at (2i+2).

initialize: i to 1 and j to 2
inside a while loop(running for (No. nodes-1)/2 times):
call compare( array[i], array[j] );
if j ==i+1 i=j+1 and j=2*i
else i++ and j--;
end while

if compare function fails: quit
otherwise if while loop runs for the required no. of times => mirror image true

we can use hash to do it

string hash(node* tree, bool left)
{
  if(tree == null)
    return goodhashfunction("0");

 if(left == true)
  return goodhashfunction(hash(tree->left) + hash(tree->right) + tree->data);
else
   return goodhashfunction(hash(tree->right) + hash(tree->left) + tree->data);
}

bool ismirror(node* tree)
{
   if(hash(tree->left, true) == hash(tree->right, false))
      return true;
   else 
      return false;
}

Another option

bool IsMirror(node* left, node* right)
{

//LOAD left AND right NODE FROM DISK
 
  if(left->data!=right->date)
    return false;
  if(left==null)
    return true;
  return IsMirror(left->right, right->left) && IsMirror(left->left, right->right);
}

bool IsMirror(node* n)
{
  IsMirror(n->left, n->right);
}

Run two DFS instances on the left and right subtrees and check if the two will see similar values. The left DFS will work the opposite of the right side DFS though: whenever you go left on the left subtree's DFS, you go right on the right subtree's DFS.

store left, thn root, thn right (i.e inorder) traversal in one line...
Now store right, then root, then left (i.e reverse inorder) in second line of a file..
both lines shud b same.. if it is then it is reflected image..

we are supposed to use iteration here since it wont take too much stack space since the tree is huge.
1) use BFS with a queue, but while enqueuing nodes enqueue

pseudo code
enqueue(root.left)
enqueue(root.right)
while(queue.size() > 0){
Node node1 = dequeue();
Node node2 = dequeue();

check if node1.data != node2.data return false;
else{
if( (node1.right == null && node2.left !=null) || (node1.right != null && node2.left ==null)
return false;
if(node1.right != null && node2.left!=null){
enqueue(node1.right);
enqueue(node2.left);
}
if(node1.left != null && node2.right!=null){
enqueue(node1.left);
enqueue(node2.right);
}
}
}

Also, each Node should have two int fields - leftId, rightId each store a unique id. we can use this id as the filename of a file in some default directory( the file stores the subtree below that node). if the leftId = -1 or (rightid = -1), we can access the child nodes as usual.
if leftid or rightid is some positive number, we should load that subtree into memory.
This approach would minimize the no. of disk reads. If we were to store each node on disk, that would require a lot of disk accesses which slow downs the execution of the program.

take two queue.. and do level wise travesal.
fetch in 1 queue one level and fetch 2nd queue its child nodes. compare queue1 nodes.doing hashing or compare it 1st node to last node and 2nd node to 2nd last node.... and so on.

now delete all node from queue now fetch the child of queue 2 in queue1 .now this time compare queue2 nodes..... and do same things.

If the tree is huge - the recursive inorder traversal will put heavy load on the system stack!
I would prefer BFS traversal using an Arraylist - the size of the arraylist will be close to (2^height of the tree).
At each iteration - you save a level in arrayList and then you compare with the other tree to check if its a mirror!