Welcome Guest ( Log In | Register)



 
 Reply to this topicStart new topic
> Data Structures -- Binary Tree -- Mirror Image, Binary Tree -- Mirror Image
varalu
post Oct 26 2007, 08:50 AM
Post #1


Super Member
*********

Group: [HOSTED]
Posts: 328
Joined: 1-October 07
From: India
Member No.: 50,968
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
CODE
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.
CODE
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....
CODE
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
CODE
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 !!");


This post has been edited by varalu: Oct 26 2007, 09:52 AM

(list)

Go to the top of the page
 
+Quote Post
« Next Oldest · Others · Next Newest »
 

Reply to this topicStart new topic

Collapse

> Similar Topics

Topics Topics
  1. Scrolling Images?(5)
  2. Data Structure Questions(4)
  3. Data Structures -- Linked List(10)
  4. Data Structures -- Binary Tree -- Structurally Same(4)
  5. Data Structures -- Linked List -- Reverse(5)
  6. Data Structures -- String -- Palindrome(5)
  7. Data Structures -- Linked List -- Point Of Merging(2)
  8. Data Structures -- String -- Arrange Based On Repetition(1)
  9. Data Structure -- Arrays -- Odd Number Of Elements(0)
  10. Data Structures -- Expression Trees(0)
  11. Data Structure -- Trees -- Threaded Binary Tree(0)
  12. Data Structure -- Queue -- Implement Using Stack(1)
  13. Data Structure -- Permutations(1)
  14. Php - Ajax: E-mail Protection, Clickable Image(2)


 

Display Mode: Standard · Switch to: Linear+ · Switch to: Outline

Track this topic · Email this topic · Print this topic · Subscribe to this forum

- Lo-Fi Version Time is now: 21st November 2008 - 07:24 AM
Powered By IP.Board © 2008  IPS, Inc.
Licensed to: Xisto Corporation