Showing posts with label Create Binary Tree. Show all posts
Showing posts with label Create Binary Tree. Show all posts

Convert a Binary Tree into its Mirror Tree

Mirror of a Tree: Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged as given below example.


Mirroring Binary Tree


public class MirroringBinaryTree {

 class NODE {

  int data;
  NODE left;
  NODE right;

  public NODE(int data) {
   this.data = data;
   left = right = null;
  }
 }

 public static void main(String[] args) {

  MirroringBinaryTree obj = new MirroringBinaryTree();

  int val[] = new int[] { 23, 34, 12, 10, 36, 35, 40, 55 };

  NODE root = obj.createBinaryTree(val);

  System.out.print("\n\n INORDER ::::::: ");
  obj.inOrderTraversal(root);

  root = obj.mirror(root);

  System.out.print("\n\n INORDER AFTER MIRROR::::::: ");
  obj.inOrderTraversal(root);
 }

 /*
  * Mirror the binary tree
  */
 public NODE mirror(NODE node) {
  if (node == null)
   return node;

  NODE left = mirror(node.left);
  NODE right = mirror(node.right);

  /* swap left and right pointers */
  node.left = right;
  node.right = left;

  return node;
 }

 /*
  *  BST in-order traversal
  */
 public void inOrderTraversal(NODE root) {

  if (root.left != null) {
   inOrderTraversal(root.left);
  }

  System.out.print(root.data + ", ");

  if (root.right != null) {
   inOrderTraversal(root.right);
  }
 }

 /*
  * Create binary tree by given array
  */
 public NODE createBinaryTree(int val[]) {
  NODE root = null;
  for (int i : val) {
   NODE tmp = new NODE(i);
   if (root == null) {
    root = tmp;
   } else {
    NODE lastNode = getLastNode(root, i);
    if (i > lastNode.data) {
     lastNode.right = tmp;
    } else {
     lastNode.left = tmp;
    }
   }
  }
  return root;
 }

 /*
  * Get parent node the join current node
  */
 public NODE getLastNode(NODE root, int val) {

  if (val > root.data) {

   if (root.right == null) {
    return root;
   } else
    return getLastNode(root.right, val);
  } else {

   if (root.left == null) {
    return root;
   } else
    return getLastNode(root.left, val);
  }
 }
}


OUTPUT:


 INORDER ::::::: 10, 12, 23, 34, 35, 36, 40, 55, 

 INORDER AFTER MIRROR::::::: 55, 40, 36, 35, 34, 23, 12, 10, 

Create Binary Tree - Preorder, Inorder and Postorder Traversal

Lets see simple java code to create Binary Tree and all 3 traversals like Preorder, Inorder and Postorder.
Used 2 classes called BST (used for binary tree node) and BinaryTree to construct Binary Tree and for traversals.

Create Binary Tree - Preorder, Inorder and Postorder Traversal
class BST {

 BST left; // Left subtree
 BST right; // Right subtree
 int data; // Element

 public BST(int data) {
  this.data = data;
 }
}



public class BinaryTree {

 public static void main(String[] args) {

  int val[] = new int[] { 4, 5, 8, 100, 3, 2, 9, 1, 7, 6 };;
  
  BST root = new BST(val[0]); // Initialize root with 1ft element
  BST tmpRoot = root; // Temporary root node

  for (int i = 1; i < val.length; i++) {

   BST lastNode = getLastNode(tmpRoot, val[i]);

   if (val[i] > lastNode.data) {

    BST tmp = new BST(val[i]);
    lastNode.right = tmp;

   } else {

    BST tmp = new BST(val[i]);
    lastNode.left = tmp;
   }
  }

  System.out.print("\n\n PREORDER :::::: ");
  preOrderTraversal(root);

  System.out.print("\n\n INORDER ::::::: ");
  inOrderTraversal(root);

  System.out.print("\n\n POSTORDR :::::: ");
  postOrderTraversal(root);
 }

 public static BST getLastNode(BST root, int val) {

  if (val > root.data) {

   if (root.right == null) {
    return root;
   } else
    return getLastNode(root.right, val);
  } else {

   if (root.left == null) {
    return root;
   } else
    return getLastNode(root.left, val);
  }
 }

 // BST Pre-order traversal
 public static void preOrderTraversal(BST root) {

  System.out.print(root.data + ", ");

  if (root.left != null) {
   preOrderTraversal(root.left);
  }
  if (root.right != null) {
   preOrderTraversal(root.right);
  }
 }

 // BST in-order traversal
 public static void inOrderTraversal(BST root) {

  if (root.left != null) {
   inOrderTraversal(root.left);
  }

  System.out.print(root.data + ", ");

  if (root.right != null) {
   inOrderTraversal(root.right);
  }
 }

 // BST post-order traversal
 public static void postOrderTraversal(BST root) {

  if (root.left != null) {
   postOrderTraversal(root.left);
  }
  if (root.right != null) {
   postOrderTraversal(root.right);
  }
  System.out.print(root.data + ", ");
 }
}



OUTPUT:

 PREORDER :::::: 4, 3, 2, 1, 5, 8, 7, 6, 100, 9, 

 INORDER ::::::: 1, 2, 3, 4, 5, 6, 7, 8, 9, 100, 

 POSTORDR :::::: 1, 2, 3, 6, 7, 9, 100, 8, 5, 4,