Wednesday, 7 December 2016

Stack implementation using Linked List

We have seen Stack implementation using array in our earlier tutorials. Now lets see same stack implementation using Linked List and how to push() and pop() values in Stack.
Below is the simple example to push() integers into Stack internally having Linked List nodes with total stack size of 10.
Stack implementation using Linked List

class NODE {
 
 NODE link;
 int data;
 
 public NODE() {
 }
 
 public NODE(int data) {
  this.data = data;
 } 
}



public class StackUsingLinkedList {

 NODE root;
 int stackSize = 0;
 int stackLimit = 10;
 
 public static void main(String[] args) {
  
  StackUsingLinkedList obj = new StackUsingLinkedList();
  
  for(int i =0;i<11;i++){
   obj.push(i+10);
  }
  
  for(int i =0;i<11;i++){
   System.out.println(obj.pop());
  }
 }
 
 private int pop(){
  if(stackSize == 0){
   System.out.println("Stack empty ....");
   return -1;   
  }
  NODE tmp = root;
  root = root.link;
  stackSize--;
  return tmp.data;
  
 }
 
 private void push(int val){
  if(stackLimit == stackSize) {
   System.out.println("Stack Full ....");
   return;
  }
  if(root == null){
   root = new NODE(val);
   root.link = null;   
  }else{
   NODE tmp = new NODE(val);
   tmp.link = root;
   root = tmp;
  }
  System.out.println("PUSH ::: "+stackSize + " :: "+val);
  stackSize++;
 }
}



OUTPUT:

PUSH ::: 0 :: 10
PUSH ::: 1 :: 11
PUSH ::: 2 :: 12
PUSH ::: 3 :: 13
PUSH ::: 4 :: 14
PUSH ::: 5 :: 15
PUSH ::: 6 :: 16
PUSH ::: 7 :: 17
PUSH ::: 8 :: 18
PUSH ::: 9 :: 19
Stack Full ....
19
18
17
16
15
14
13
12
11
10
Stack empty ....
-1

read more.. "Stack implementation using Linked List "

Monday, 5 December 2016

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, 

read more.. "Create Binary Tree - Preorder, Inorder and Postorder Traversal "