Pages
Showing posts sorted by date for query binary tree. Sort by relevance Show all posts
Showing posts sorted by date for query binary tree. Sort by relevance Show all posts

Inorder Predecessor and Successor of Binary Search Tree

 
In a given Binary Search Tree need to find the predecessor and Successor of a given node.

What is Predecessor and Successor ?

In a given Binary Search Tree highest element on the left subtree is the Predecessor and lowest element on the right subtree is the Successor of the given node. For example in a below given binary search tree if we need to find Predecessor and Successor of node 28

Inorder Predecessor and Successor of Binary Search Tree


then, node 20 will be the Predecessor and node 36 will be the Successor.

Lets see simple example as how to find Inorder Predecessor and Successor for any given binary tree.


public class PredecessorSuccessor {

 class BST {

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

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

 private int predecessor = -1;
 private int successor = -1;
 private int previous = -1;

 public static void main(String[] args) {

  int val[] = new int[] { 28, 15, 40, 19, 10, 36, 45, 20, 5, 50 };

  int findPreSuc = 28;
  
  PredecessorSuccessor obj = new PredecessorSuccessor();

  BST root = obj.createBST(val);

  obj.getPredecessorSuccessor(root, findPreSuc);
  
  System.out.println("Given node element : "+findPreSuc);
  
  if(obj.predecessor == -1) {
   System.out.println("No Predecessor for the given node ");
  }else {
   System.out.println("Predecessor : " + obj.predecessor);

  }if(obj.successor == -1) {
   System.out.println("No Successor for the given node ");
  }else {
   System.out.println("Successor : " + obj.successor);

  }
 }

 // BST in-order traversal
 public void getPredecessorSuccessor(BST root, int findPreSuc) {

  // Return once we got both Predecessor and Successor
  if (predecessor != -1 && successor != -1) {
   return;
  }

  // Recursive to left subtree
  if (root.left != null) {
   getPredecessorSuccessor(root.left, findPreSuc);
  }

  // Getting Predecessor
  if (root.data == findPreSuc) {
   predecessor = previous;
  }

  // Getting Successor
  if (findPreSuc == previous) {
   successor = root.data;
   previous = root.data;
   return;
  }
  previous = root.data;
  
  // Recursive to right subtree
  if (root.right != null) {
   getPredecessorSuccessor(root.right, findPreSuc);
  }

 }

 public BST createBST(int[] val) {

  BST root = new BST(val[0]); // Root node with 1st element
  BST tmpRoot = root;

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

  return root;
 }

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


OUTPUT:


Given node element : 28
Predecessor : 20
Successor : 36


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,

Sorting Integer array without any sorting algorithm or loop ?

 
In this tutorial we will see about how to sort and print the integer array without using any sorting algorithm or without using any loop to sort.
Here it comes the Data Structure and we are going to use Binary Search Tree with In-order traversal. Just need to create BST with the given array and traverse through BST using In-order traversal. By this way we can sort given array without using any sorting algorithm or loop to sort the given array.
Sorting Array


Lets see simple Java code how to create BST with the given integer array and to traverse through BST and print the given array in sorted order.


class BST {

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

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


public class SortingWithoutLoop {

 public static void main(String[] args) {

  int val[] = new int[] { 5, 8, 3, 7, 0, 43, 65, 8, 2, 89, 25 };
  BST root = new BST(val[0]);
  for (int i = 1; i < val.length; i++) {
   BST lastNode = getLastNode(root, 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;
   }
  }
  
  inOrderTraversal(root);
 }

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

  if (root.right != null && val > root.data) {
   return getLastNode(root.right, val);
  } else if(root.left != null && val < root.data){
   return getLastNode(root.left, val);
  }
  return root;
 }

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


OUTPUT:


0, 2, 3, 5, 8, 8, 25, 43, 65, 89,

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,

Get updates in your email box

Complete the form below, and we'll send you our recent update.

Deliver via FeedBurner
© Copyright 2015 Java Discover. Designed by Bloggertheme9 | Distributed By Gooyaabi Templates. Powered by Blogger.