xisto Community

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

## Recommended Posts

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 !!");`
Edited by varalu (see edit history)

##### Share on other sites
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

##### Share on other sites

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;

}

##### Share on other sites

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

##### Share on other sites

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

##### Share on other sites

//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;}`

##### Share on other sites

// 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;}`

## Create an account

Register a new account