# Data Structures -- Binary Tree -- Mirror Image Binary Tree -- Mirror Image

### varalu

Given a binary tree, write an algorithm to find its mirror image with minimal time and space complexities.

Note: If you know the answer and if you feel it is simple also please post the answers so that others will come to know about the answers.

This question was sent by my friend through mail.

Solutions Suggested

Sol 1

void PrintMirror(node *root){ if(node!=NULL) PrintMirror(root->right); Printf(root->data); PrintMirror(root->left); }
In case of implementation using array 2i+1 stores left child of ith node and 2i+2 stores right element.

for(int i=0;i<(2^levels)-1;i++){ swap(tree[2i+1],tree[2i+2]);}
Note: Null nodes are also to be swaped hence (2^levels)-1 -- Suggested by my friend...

Sol 2

Another Solution....

void Mirror(node *ptr){ if(ptr!=(node *) NULL) { node* right=ptr->right; Mirror(ptr->left); Mirror(ptr->right); ptr->right=ptr->left; ptr->left=right; }}
Time complexity : O(n). Each node is processed once.

Space complexity : only one temp ptr used.

More solutions welcome...

Notice from rvalkass:

Double post merged. Remember the edit button is available for you to use. Also, any code needs to be in CODE tags.

One more Solution here...

Sol 3

One more algo

node* mirror(node **tree){ node * temptree; if(*tree!=(node*)NULL) { temptree =(node*)malloc(sizeof(node)); temptree->left = mirror(tree->right); temptree->data = tree->data; temptree->right = mirror(tree->left); return(temptree); } else printf("Tree is empty !!");

### iGuest

Binomail Queues - Merging itselfData Structures -- Binary Tree -- Mirror ImageWhat happens when a Binomial queue merges with itself?And also, if this is possible give me the code in C.Reference:Chapter 6 Excercise: 6.32DataStructures and algortihm analysis in C, Second EditionAuthor: Mark Allen WeissThanks

### iGuest

void FlipTree(Node* node)

{

if(node == NULL) return;

FlipTree(node->Right);

FlipTree(node->Left);

Node* tmp;

tmp = node->Right;

node->Right = node->Left;

node->Left = tmp;

}

### iGuest

Suppose that you are a financier and purchase 100 shares of stock in Company X in eachOf January, April, and September and sell 100 shares in each of June and November. ThePrices per share in these months wereJan Apr Jun Sep Nov\$10 \$30 \$20 \$50 \$30Determine the total amount of your capital gain or loss using(I) FIFO (first-in, first-out) accounting and(ii) LIFO (last-in, first-out) accounting[That is, assuming that you keep your stock certificates in (a) a queue or ( a stack]. The100 shares you still own at the end of the year do not enter the calculation.-reply by abuenad

### iGuest

can u write it without using recursion....???

### iGuest

//C++

nodebt* nodebt::mirrorimage(class bin_tree *r,class bin_tree* m){ nodebt *ret=NULL; if(r==NULL) return r; if(r->status==2) { nodebt *temp=new nodebt; temp->data=r->data; temp->status=2; m=temp; ret=temp; } if(r->status==0) { nodebt *temp=new nodebt; temp->data=r->data; temp->status=1; m->rchild=temp; m=m->rchild; } if(r->status==1) { nodebt *temp=new nodebt; temp->data=r->data; temp->status=0; m->lchild=temp; m=m->lchild; } mirrorimage(r->lchild,m); mirrorimage(r->rchild,m); return ret;}

### iGuest

// This Is Code For C Language Programming

#include<stdio.h>#include<stdlib.h>/* 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;};/* Helper 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);}/* Change a tree so that the roles of the left and right pointers are swapped at every node.So the tree... 4 / \ 2 5 / \ 1 3is changed to... 4 / \ 5 2 / \ 3 1*/void mirror(struct node* node){ if (node==NULL) return; else { struct node* temp; /* do the subtrees */ mirror(node->left); mirror(node->right); /* swap the pointers in this node */ temp = node->left; node->left = node->right; node->right = temp; }}/* Helper function to test mirror(). Given a binary search tree, print out its data elements in increasing sorted order.*/void inOrder(struct node* node){ if (node == NULL) return; inOrder(node->left); printf("%d ", node->data); inOrder(node->right);}/* Driver program to test mirror() */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); /* Print inorder traversal of the input tree */ printf("\n Inorder traversal of the constructed tree is \n"); inOrder(root); /* Convert tree to its mirror */ mirror(root); /* Print inorder traversal of the mirror tree */ printf("\n Inorder traversal of the mirror tree is \n"); inOrder(root); getchar(); return 0;}

 VIEW DESKTOP VERSION REGISTER GET FREE HOSTING