m2skills

mirror iter bt java

Jun 4th, 2018
48
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.97 KB | None | 0 0
  1. // http://code2begin.blogspot.com
  2. // program to create mirror of a given binary tree recursively
  3.  
  4. /**
  5.  * Created by MOHIT on 25-05-2018.
  6.  */
  7. import java.util.*;
  8. import static java.lang.Integer.max;
  9.  
  10. // node class
  11. class node{
  12.     int data;
  13.     node left;
  14.     node right;
  15.  
  16.     // function that returns a pointer to new node
  17.     public node(int element){
  18.         this.data = element;
  19.         this.left = null;
  20.         this.right = null;
  21.        
  22.     }
  23. };
  24.  
  25.  
  26. public class BinaryTree {
  27.    
  28.     // function to convert tree into mirror tree iteratively
  29.     static void mirror_tree(node root){
  30.         // if the node is null then return
  31.         if (root == null){
  32.         return;
  33.         }
  34.    
  35.         // creating a stack to keep the child pointers
  36.         Stack STACK = new Stack<node>();
  37.    
  38.         // push root node on the stack
  39.         STACK.push(root);
  40.    
  41.         while (!STACK.isEmpty()){
  42.    
  43.             // remove the top node from the stack
  44.             node current = (node)STACK.peek();
  45.             STACK.pop();
  46.    
  47.             // swap the left and right nodes
  48.             node temp = current.left;
  49.             current.left = current.right;
  50.             current.right = temp;
  51.    
  52.             // as it is a stack, we push right child node first because we want to access it after operating on the left child
  53.             if (current.right != null){
  54.                 STACK.push(current.right);
  55.             }
  56.             if (current.left != null){
  57.                 STACK.push(current.left);
  58.             }
  59.         }
  60.     }
  61.    
  62.     // function to print the preorder traversal of a binary tree
  63.     public static void preorder(node root) {
  64.         if (root == null) {
  65.             return;
  66.         }
  67.         System.out.print(root.data + " ");
  68.         preorder(root.left);
  69.         preorder(root.right);
  70.     }
  71.  
  72.  
  73.     public static void main(String arg[]) {
  74.         node m1 = new node(8);
  75.         m1.left = new node(3);
  76.         m1.right = new node(10);
  77.         m1.left.left = new node(1);
  78.         m1.left.right = new node(6);
  79.         m1.left.right.left = new node(4);
  80.         m1.left.right.right = new node(7);
  81.         m1.right.right = new node(14);
  82.         m1.right.right.left = new node(13);
  83.  
  84.         node m2 = new node(8);
  85.         m2.right = new node(3);
  86.         m2.left = new node(10);
  87.         m2.left.left = new node(14);
  88.         m2.right.left = new node(6);
  89.         m2.right.right = new node(1);
  90.         m2.left.left.right = new node(13);
  91.         m2.right.left.left = new node(7);
  92.         m2.right.left.right = new node(4);
  93.  
  94.         System.out.println("Tree #1 before mirroring : ");
  95.         preorder(m1);
  96.         System.out.println("\nTree #1 after mirroring : ");
  97.         mirror_tree(m1);
  98.         preorder(m1);
  99.         System.out.println("\n\nTree #2 is mirror of Tree #1 to check the correctness : ");
  100.         System.out.println("TREE #1 : ");
  101.         preorder(m1);
  102.         System.out.println("\nTREE #2 : ");
  103.         preorder(m2);
  104.  
  105.     }
  106. }
Add Comment
Please, Sign In to add comment