7 replies to this topic

[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 !!");

Edited by varalu, 26 October 2007 - 09:52 AM.

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

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]

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 (b) a stack]. The100 shares you still own at the end of the year do not enter the calculation.-reply by abuenad

[iGuest]

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