1 Oct 2013

Mirror Binary Tree

Problem Statement:
       Create a mirror of the given Tree

Solution: 

In this problem we are modifying the tree to produce the mirror of the tree. Therefore the existing tree is modified.
The logic behind this problem is swapping the left and right child of every node.
Post order traversal and swapping is used to achieve the objective.

 Pls refer to the working code from the given link.
Source Code

  /**
  * Create Mirror of a Tree
  * @param root of a tree
  */
 public void mirror(Node root) {
  if(root== null)
   return ;
  
  else
  {
   mirror(root.left);
   mirror(root.right);

   swap(root);
  }
 }

 // Swap Sub-Trees of a Node
 private void swap(Node node) {
  Node temp=node.right;
  node.right=node.left;
  node.left=temp;
 }


Now we are a creating a copy of the current tree such that the tree produced is mirror of the given tree.



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
       private Node mirror(Node root){
 
 if(root==null)
 return null;
 
 Node newRoot= new Node(root.data);
 newRoot.left = mirror(root.right) ;
 newRoot.right = mirror(root.left) ;
 
 return newRoot;
     }

Please post comment or suggest if any improvisation possible to the given logic .

Happy Coding :)

No comments:

Post a Comment