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

[varalu 0]

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 October 26, 2007 by varalu (see edit history)

[iGuest 3]

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 3]

How about this?Data Structures -- Binary Tree -- Mirror Image

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;

}

-reply by TryThis

[iGuest 3]

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 3]

import javax.Swing.*;Import java.Awt.*;Import java.Awt.Event.*;public class JCheckBoxEventPrice extends JFrame implements ItemListener{  int basePrice = 300;  int weekendPremium = 100;  int guestPremium = 200;  int entPremium = 400;  int totalPrice = basePrice;      JCheckBox weekendBox = new JCheckBox ("Weekend premium Php"+ weekendPremium, false);  JCheckBox guestBox = new JCheckBox ("Over 200 guests Php"+ guestPremium, false);  JCheckBox entBox = new JCheckBox ("Live entertainment Php"+ entPremium, false);      JLabel eventHandLabel = new JLabel ("Event Handlers Incorporated");  JLabel ePrice = new JLabel ("the price for your event is ");  JTextField totPrice = new JTextField(10);  JLabel optionExplainLabel1 = new JLabel ("Base price for an event is Php" + basePrice+".");  JLabel optionExplainLabel2 = new JLabel ("Check the options you want.");  public JCheckBoxEventPrice()  {    super ("Event Price Estimator");    setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);    JPanel pane = new JPanel();        pane.Add(eventHandLabel);    pane.Add(optionExplainLabel1);    pane.Add(optionExplainLabel2);    pane.Add(weekendBox);    pane.Add(guestBox);    pane.Add(entBox);    pane.Add(ePrice);    pane.Add(totPrice);            totPrice.SetText("Php"+totPrice);    weekendBox.AddItemListener(this);    guestBox.AddItemListener(this);    entBox.AddItemListener(this);            setContentPane(pane);      }  public void itemStateChanged(ItemEvent e)  {    Object source = e.GetSource();    int select = e.GetStateChange();        if(source == weekendBox)      if(select == ItemEvent.SELECTED)        totalPrice+=weekendPremium;      else        totalPrice-=weekendPremium;    else if(source==guestBox)    {      if(select == ItemEvent.SELECTED)        totalPrice+=guestPremium;      else        totalPrice-=guestPremium;    }    else      if(select == ItemEvent.SELECTED)        totalPrice+=entPremium;      else        totalPrice-=entPremium;      totPrice.SetText("Php"+totalPrice);    }  public static void main (String[] args)  {    JFrame aFrame = new JCheckBoxEventPrice();    aFrame.SetSize(300,250);    aFrame.SetVisible(true);  }}

[iGuest 3]

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

[iGuest 3]

//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 3]

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