If you want to practice data structure and algorithm programs, you can go through 100+ data structure and algorithm programs.

In this post, we will see how to generate all subarrays of given array.

Problem

Print all print all subarrays of given array.
For example:

Solution

If there are n elements in the array then there will be (n*n+1)/2 subarrays.
Here is a simple algorithm for it.

• We will use three loop to print subarrays.
• Outer loop will be used to get start index
• First inner loop will be used to get end index
• Second inner loop will be used to print element from start to end index.

here is simple program to print all subarrays of given array..

package org.arpit.java2blog;

public class PrintSubarrayMain {

    public static void main(String args[]){
        PrintSubarrayMain psm=new PrintSubarrayMain();
        int arr[]= {1,2,3,4};
        psm.printSubArray(arr);
    }

    void printSubArray(int arr[])
    {

        int n=arr.length;
        for (int i=0; i <n; i++) //This loop will select start element
        {
            for (int j=i; j<n; j++) // This loop will select end element
            {
                for (int k=i; k<=j; k++) //This loop will print element from start to end
                {
                    System.out.print( arr[k]+" "); 
                }
                System.out.println();
            }
        }
    }
}

That’s all about how to generate all subarrays of a given array

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

In this post, we will see Dijkstra algorithm for find shortest path from source to all other vertices.

Problem

You will be given graph with weight for each edge,source vertex and you need to find minimum distance from source vertex to rest of the vertices.

Algorithm

There will be two core classes, we are going to use for Dijkstra algorithm.
Vertex: This class contains name, visited flag, predecessor(To track the short path, so that we can backtrack) and distance from source node and also the list of outgoing edge from this vertex.
Edge: This class contains Source vertex, target vertex, and weight.

Let’s first understand how are we going to solve it visually.

As you can see, we have initialized predecessor and minimum distance to default.Green node represents visited nodes and red color represent neighbors of the vertex.

Here we are considering :

Total distance from source vertex A to vertex B via vertex C: 15

Total distance from source vertex A to vertex D via vertex C: 19

Total distance from source vertex A to vertex E via vertex C: 21

As distance from C to B is minimum i.e 15, that’s why we have chosen vertex B as next vertex.

As you can see, we are done with Dijkstra algorithm and got minimum distances from Source Vertex A to rest of the vertices.

Let me go through core algorithm for Dijkstra.

• Set distance for source Vertex to 0.
• Set distance for all other vertices to infinity.
• At each vertex, we need to choose a node with minimum distance from source vertex and we are going to use priority queue for that.
• Add source node to PriorityQueue.
• Do the following when PriorityQueue is not empty
  • Poll vertex (Let’ say vertex A) from the PriorityQueue.
  • Iterate over neighbours(Let’s say Vertex B) for the vertex A.
  • Calculate new distance for vertex B by adding vertex.getDistance and edge.getWeight
  • If new distance <  Vertex B’s current distance then update the node(Distance,predecessor) in PriorityQueue.

public void computeShortestPaths(Vertex sourceVertex){

        sourceVertex.setDistance(0);
        PriorityQueue<Vertex> priorityQueue = new PriorityQueue<>();
        priorityQueue.add(sourceVertex);
        sourceVertex.setVisited(true);

        while( !priorityQueue.isEmpty() ){
            // Getting the minimum distance vertex from priority queue
            Vertex actualVertex = priorityQueue.poll();

            for(Edge edge : actualVertex.getAdjacenciesList()){

                Vertex v = edge.getTargetVertex();
                if(!v.isVisited())
                {
                    double newDistance = actualVertex.getDistance() + edge.getWeight();

                    if( newDistance < v.getDistance() ){
                        priorityQueue.remove(v);
                        v.setDistance(newDistance);
                        v.setPredecessor(actualVertex);
                        priorityQueue.add(v);
                    }
                }
            }
            actualVertex.setVisited(true);
        }
    }

Let’s see complete source code for Dijkstra’s algorithm

Dijkstra’s algorithm example

Create a class named Vertex.java as below:

package org.arpit.java2blog.algo;

import java.util.ArrayList;
import java.util.List;

public class Vertex implements Comparable<Vertex> {

    private String name;
    private List<Edge> adjacenciesList;
    private boolean visited;
    private Vertex predecessor;
    private double distance = Double.MAX_VALUE;

    public Vertex(String name) {
        this.name = name;
        this.adjacenciesList = new ArrayList<>();
    }

    public void addNeighbour(Edge edge) {
        this.adjacenciesList.add(edge);
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public List<Edge> getAdjacenciesList() {
        return adjacenciesList;
    }

    public void setAdjacenciesList(List<Edge> adjacenciesList) {
        this.adjacenciesList = adjacenciesList;
    }

    public boolean isVisited() {
        return visited;
    }

    public void setVisited(boolean visited) {
        this.visited = visited;
    }

    public Vertex getPredecessor() {
        return predecessor;
    }

    public void setPredecessor(Vertex predecessor) {
        this.predecessor = predecessor;
    }

    public double getDistance() {
        return distance;
    }

    public void setDistance(double distance) {
        this.distance = distance;
    }

    @Override
    public String toString() {
        return this.name;
    }

    @Override
    public int compareTo(Vertex otherVertex) {
        return Double.compare(this.distance, otherVertex.getDistance());
    }
}

Create another class named Edge.java as below.

package org.arpit.java2blog.algo;

public class Edge {

    private double weight;
    private Vertex startVertex;
    private Vertex targetVertex;

    public Edge(double weight, Vertex startVertex, Vertex targetVertex) {
        this.weight = weight;
        this.startVertex = startVertex;
        this.targetVertex = targetVertex;
    }

    public double getWeight() {
        return weight;
    }

    public void setWeight(double weight) {
        this.weight = weight;
    }

    public Vertex getStartVertex() {
        return startVertex;
    }

    public void setStartVertex(Vertex startVertex) {
        this.startVertex = startVertex;
    }

    public Vertex getTargetVertex() {
        return targetVertex;
    }

    public void setTargetVertex(Vertex targetVertex) {
        this.targetVertex = targetVertex;
    }
}

Create another class named "DijkstraShortestPath.java" as below. This will contain main Dijkstra algorithm.

package org.arpit.java2blog.algo;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public class DijkstraShortestPath {

    public void computeShortestPaths(Vertex sourceVertex){

        sourceVertex.setDistance(0);
        PriorityQueue<Vertex> priorityQueue = new PriorityQueue<>();
        priorityQueue.add(sourceVertex);
        sourceVertex.setVisited(true);

        while( !priorityQueue.isEmpty() ){
            // Getting the minimum distance vertex from priority queue
            Vertex actualVertex = priorityQueue.poll();

            for(Edge edge : actualVertex.getAdjacenciesList()){

                Vertex v = edge.getTargetVertex();
                if(!v.isVisited())
                {
                    double newDistance = actualVertex.getDistance() + edge.getWeight();

                    if( newDistance < v.getDistance() ){
                        priorityQueue.remove(v);
                        v.setDistance(newDistance);
                        v.setPredecessor(actualVertex);
                        priorityQueue.add(v);
                    }
                }
            }
            actualVertex.setVisited(true);
        }
    }

    public List<Vertex> getShortestPathTo(Vertex targetVertex){
        List<Vertex> path = new ArrayList<>();

        for(Vertex vertex=targetVertex;vertex!=null;vertex=vertex.getPredecessor()){
            path.add(vertex);
        }

        Collections.reverse(path);
        return path;
    }

}

Create another class named "DijkstraMain.java". This class will contain main function to run the algorithm.

package org.arpit.java2blog.algo;

public class DijkstraMain {

    public static void main(String[] args) {

        Vertex vertexA = new Vertex("A");
        Vertex vertexB = new Vertex("B");
        Vertex vertexC = new Vertex("C");
        Vertex vertexD = new Vertex("D");
        Vertex vertexE = new Vertex("E");

        vertexA.addNeighbour(new Edge(10,vertexA,vertexC));
        vertexA.addNeighbour(new Edge(17,vertexA,vertexB));
        vertexC.addNeighbour(new Edge(5,vertexC,vertexB));
        vertexC.addNeighbour(new Edge(9,vertexC,vertexD));
        vertexC.addNeighbour(new Edge(11,vertexC,vertexE));
        vertexB.addNeighbour(new Edge(1,vertexB,vertexD));
        vertexD.addNeighbour(new Edge(6,vertexD,vertexE));

        DijkstraShortestPath shortestPath = new DijkstraShortestPath();
        shortestPath.computeShortestPaths(vertexA);

        System.out.println("======================================");
        System.out.println("Calculating minimum distance");
        System.out.println("======================================");

        System.out.println("Minimum distance from A to B: "+vertexB.getDistance());
        System.out.println("Minimum distance from A to C: "+vertexC.getDistance());
        System.out.println("Minimum distance from A to D: "+vertexD.getDistance());
        System.out.println("Minimum distance from A to E: "+vertexE.getDistance());

        System.out.println("=====================   =================");
        System.out.println("Calculating Paths");
        System.out.println("======================================");

        System.out.println("Shortest Path from A to B: "+shortestPath.getShortestPathTo(vertexB));
        System.out.println("Shortest Path from A to C: "+shortestPath.getShortestPathTo(vertexC));
        System.out.println("Shortest Path from A to D: "+shortestPath.getShortestPathTo(vertexD));
        System.out.println("Shortest Path from A to E: "+shortestPath.getShortestPathTo(vertexE));

    }
}

When you run above program, you will get below output:

That’s all about Dijkstra algorithm in java.

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

In this post, we will see about Doubly LinkedList implementation in java.
We have already seen the implementation of singly linked list. You can consider this as an extension of Singly linked list.It is quite complex to implement it as compared to singly linked list.
In doubly linked list, Node has data and pointers to next node and previous node. First node’s previous points to null and Last node‘s next also points to null, so you can iterate over linked list in both direction with these next and previous pointers.
An example of Doubly Linked List:

Node for doubly linked list can be presented as below:

class Node {
    public int data;
    public Node next;
    public Node prev;

    public void displayNodeData() {
        System.out.println("{ " + data + " } ");
    }
}

As you can see, we have one more extra reference(Node prev) in case of doubly linked list.
Let’s say, you want to do insert First operation in case of Doubly linked list, it will look like as below:

Doubly linked list in java example

Let’s implement Doubly Linked List in java.

Create a java file named DoublyLinkedList.java.

package org.arpit.java2blog.algo;

class Node {
    public int data;
    public Node next;
    public Node prev;

    public void displayNodeData() {
        System.out.println("{ " + data + " } ");
    }
}

public class DoublyLinkedList {

    private Node head;
    private Node tail;
    int size;

    public boolean isEmpty() {
        return (head == null);
    }

    // used to insert a node at the start of linked list
    public void insertFirst(int data) {
        Node newNode = new Node();
        newNode.data = data;
        newNode.next = head;
        newNode.prev=null;
        if(head!=null)
            head.prev=newNode;
        head = newNode;
        if(tail==null)
            tail=newNode;
        size++;
    }

    // used to insert a node at the start of linked list
    public void insertLast(int data) {
        Node newNode = new Node();
        newNode.data = data;
        newNode.next = null;
        newNode.prev=tail;
        if(tail!=null)
            tail.next=newNode;
        tail = newNode;
        if(head==null)
            head=newNode;
        size++;
    }
    // used to delete node from start of Doubly linked list
    public Node deleteFirst() {

        if (size == 0) 
            throw new RuntimeException("Doubly linked list is already empty");
        Node temp = head;
        head = head.next;
        head.prev = null;
        size--;
        return temp;
    }

    // used to delete node from last of Doubly linked list
    public Node deleteLast() {

        Node temp = tail;
        tail = tail.prev;
        tail.next=null;
        size--;
        return temp;
    }

    // Use to delete node after particular node
    public void deleteAfter(Node after) {
        Node temp = head;
        while (temp.next != null && temp.data != after.data) {
            temp = temp.next;
        }
        if (temp.next != null)
            temp.next.next.prev=temp;
        temp.next = temp.next.next;

    }

    // For printing Doubly Linked List forward
    public void printLinkedListForward() {
        System.out.println("Printing Doubly LinkedList (head --> tail) ");
        Node current = head;
        while (current != null) {
            current.displayNodeData();
            current = current.next;
        }
        System.out.println();
    }

    // For printing Doubly Linked List forward
    public void printLinkedListBackward() {
        System.out.println("Printing Doubly LinkedList (tail --> head) ");
        Node current = tail;
        while (current != null) {
            current.displayNodeData();
            current = current.prev;
        }
        System.out.println();
    }
}

Create another class named DoubleLinkedListMain as below:

package org.arpit.java2blog.algo;

public class DoubleLinkedListMain {

 public static void main(String args[])
 {
   DoublyLinkedList myLinkedlist = new DoublyLinkedList();
   myLinkedlist.insertFirst(5);
   myLinkedlist.insertFirst(6);
   myLinkedlist.insertFirst(7);
   myLinkedlist.insertFirst(1);
   myLinkedlist.insertLast(2);
   myLinkedlist.printLinkedListForward();
   myLinkedlist.printLinkedListBackward();

   System.out.println("================");
   // Doubly Linked list will be 
   // 1 ->  7 -> 6 -> 5 -> 2

   Node node=new Node();
   node.data=1;
   myLinkedlist.deleteAfter(node);
   myLinkedlist.printLinkedListForward();
   myLinkedlist.printLinkedListBackward();
   // After deleting node after 1,doubly Linked list will be 
   // 2 -> 1 -> 6 -> 5
   System.out.println("================");
   myLinkedlist.deleteFirst();
   myLinkedlist.deleteLast();

   // After performing above operation, doubly Linked list will be 
   //  6 -> 5
   myLinkedlist.printLinkedListForward();
   myLinkedlist.printLinkedListBackward();
 }
}

When you run above program, you will get below output:

That’s all about Doubly linked list in java.

If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions.

In this post, we will see about trie data structure in java.

What is Trie :

Trie is data structure which stores data in such a way that it can be retrieved faster and improve the performance.

Some real time examples:

Trie can be used to implement :
Dictionary
Searching contact in mobile phone book. 

Trie data structure:

You can insert words in trie and its children linked list will represent its child nodes and isEnd defines if it is end for the word.
Example:
Lets say, you want to insert do, deal , dear , he , hen , heat etc.
Your trie structure will look like as below:

TrieNode will have following variables and method.

class TrieNode
{
 char data;
 boolean isEnd;
 int count;
 LinkedList childList;

 /* Constructor */
 public TrieNode(char c)
 {
 childList = new LinkedList();
 isEnd = false;
 data = c;
 count = 0;
 }
 public TrieNode getChild(char c)
 {
 if (childList != null)
 for (TrieNode eachChild : childList)
 if (eachChild.data == c)
 return eachChild;
 return null;
 }
}

Each TrieNode have access to its children if present at all. It contains current data, count , isEnd and childList. isEnd is a boolean variable which represents if current Trie node is end of word or not.childList will have list of children for that TrieNode.

Algorithm for inserting word in Trie structure:

• If word already exists, return it.
• Make current node as root trie node
• Iterate over each character(lets say c) of word.
• get child trie nodes for current node
  • If child node exists and is equal to character c then make it current node and increment the count.
  • If child node does not exist, then create a new trie node with character c and add it to current node childList and change current node to newly created trie node.
• When you reach at end of the word, make isEnd = true.

Java Code:

/* This function is used to insert a word in trie*/
    public void insert(String word)
    {
        if (search(word) == true)
            return;
        TrieNode current = root;
        for (char ch : word.toCharArray() )
        {
            TrieNode child = current.getChild(ch);
            if (child != null)
                current = child;
            else
            {
             // If child not present, adding it io the list
                 current.childList.add(new TrieNode(ch));
                 current = current.getChild(ch);
            }
            current.count++;
        }
        current.isEnd = true;
    }

Algorithm for searching a word in Trie data structure:

• For each character of word , see if child node exists for it.
  • If child node does not exists, return false
• If character exists, repeat above step
• When you reach at end of the String and current.isEnd is true then return true else return false.

/* This function is used to search a word in trie*/
    public boolean search(String word)
    {
        TrieNode current = root;
        for (char ch : word.toCharArray() )
        {
            if (current.getChild(ch) == null)
                return false;
            else
                current = current.getChild(ch);
        }
        if (current.isEnd == true)
            return true;
        return false;
    }

Java code to implement Trie data structure

package org.arpit.java2blog;
/*
 *  Java Program to Implement Trie
 */

import java.util.*;

class TrieNode
{
    char data;
    boolean isEnd;
    int count;
    LinkedList childList;

    /* Constructor */
    public TrieNode(char c)
    {
        childList = new LinkedList();
        isEnd = false;
        data = c;
        count = 0;
    }
    public TrieNode getChild(char c)
    {
        if (childList != null)
            for (TrieNode eachChild : childList)
                if (eachChild.data == c)
                    return eachChild;
        return null;
    }
}

public class TrieDataStructure
{
    private TrieNode root;

     /* Constructor */
    public TrieDataStructure()
    {
        root = new TrieNode(' ');
    }
    /* This function is used to insert a word in trie*/
    public void insert(String word)
    {
        if (search(word) == true)
            return;
        TrieNode current = root;
        for (char ch : word.toCharArray() )
        {
            TrieNode child = current.getChild(ch);
            if (child != null)
                current = child;
            else
            {
             // If child not present, adding it io the list
                 current.childList.add(new TrieNode(ch));
                 current = current.getChild(ch);
            }
            current.count++;
        }
        current.isEnd = true;
    }
    /* This function is used to search a word in trie*/
    public boolean search(String word)
    {
        TrieNode current = root;
        for (char ch : word.toCharArray() )
        {
            if (current.getChild(ch) == null)
                return false;
            else
                current = current.getChild(ch);
        }
        if (current.isEnd == true)
            return true;
        return false;
    }
    /* This function is used to remove function from trie*/
    public void remove(String word)
    {
        if (search(word) == false)
        {
            System.out.println(word +" does not present in trien");
            return;
        }
        TrieNode current = root;
        for (char ch : word.toCharArray())
        {
            TrieNode child = current.getChild(ch);
            if (child.count == 1)
            {
                current.childList.remove(child);
                return;
            }
            else
            {
                child.count--;
                current = child;
            }
        }
        current.isEnd = false;
    }

    public static void printAllWordsInTrie(TrieNode root,String s)
    {
      TrieNode current = root;
      if(root.childList==null || root.childList.size()==0)
       return;
      Iterator iter=current.childList.iterator();
     while(iter.hasNext())
     {
      TrieNode node= iter.next();
      s+=node.data;
      printAllWordsInTrie(node,s);
      if(node.isEnd==true)
      {
       System.out.print(" "+s);
       s=s.substring(0,s.length()-1);
      }
      else
      {
       s=s.substring(0,s.length()-1);
      }
     }

    }
    public static void main(String[] args)
    {
        TrieDataStructure t = new TrieDataStructure();
        t.insert("dear");
        t.insert("deal");
        t.insert("do");
        t.insert("he");
        t.insert("hen");
        t.insert("heat");

        System.out.println("hen present in trie : "+t.search("hen"));
        System.out.println("hear present in trie : "+t.search("hear"));
        System.out.println("deal present in trie : "+t.search("deal"));
        System.out.println("========================");
        System.out.println("Printing all word present in trie : ");
        printAllWordsInTrie(t.root,"");
    }
}

When you run above program, you will get below output

hen present in trie : true
hear present in trie : false
deal present in trie : true
========================
Printing all word present in trie :
 dear deal do hen heat he

If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions.

In this post , we will see how to implement Queue using Linked List in java.
Queue is abstract data type which demonstrates First in first out (FIFO) behaviour. We will implement same behaviour using Array.
Although java provides implementation for  all abstract data types such as Stack , Queue and LinkedList but it is always good idea to understand basic data structures and implement them yourself.
Please note that LinkedList implementation of Queue is dynamic in nature.
There are two most important operations of Queue:
enqueue : It is operation when we insert element into the queue.
dequeue : It is operation when we remove element from the queue. Read more at

Java Program to implement Queue using Linked List:

package org.arpit.java2blog;
public class QueueUsingLinkedListMain
{
 private Node front, rear; 
 private int currentSize; // number of items

 //class to define linked node
 private class Node
 { 
 int data;
 Node next;
 }

 //Zero argument constructor
 public QueueUsingLinkedListMain()
 {
 front = null;
 rear = null;
 currentSize = 0;
 }

 public boolean isEmpty()
 {
 return (currentSize == 0);
 }

 //Remove item from the beginning of the list.
 public int dequeue()
 {
 int data = front.data;
 front = front.next;
 if (isEmpty()) 
 {
 rear = null;
 }
 currentSize--;
 System.out.println(data+ " removed from the queue");
 return data;
 }

 //Add data to the end of the list.
 public void enqueue(int data)
 {
 Node oldRear = rear;
 rear = new Node();
 rear.data = data;
 rear.next = null;
 if (isEmpty()) 
 {
 front = rear;
 }
 else 
 {
 oldRear.next = rear;
 }
 currentSize++;
 System.out.println(data+ " added to the queue");
 }
 public static void main(String a[]){

 QueueUsingLinkedListMain queue = new QueueUsingLinkedListMain();
 queue.enqueue(6);
 queue.dequeue();
 queue.enqueue(3);
 queue.enqueue(99);
 queue.enqueue(56);
 queue.dequeue();
 queue.enqueue(43);
 queue.dequeue();
 queue.enqueue(89);
 queue.enqueue(77);
 queue.dequeue();
 queue.enqueue(32);
 queue.enqueue(232);
 }
}

6 added to the queue
6 removed from the queue
3 added to the queue
99 added to the queue
56 added to the queue
3 removed from the queue
43 added to the queue
99 removed from the queue
89 added to the queue
77 added to the queue
56 removed from the queue
32 added to the queue
232 added to the queue

If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions.

package org.arpit.java2blog.binarysearchtree;

public class BinarySearchTreeSortedArrayMain {
    public static class TreeNode {
        int data;
        TreeNode left;
        TreeNode right;

        TreeNode(int data) {
            this.data = data;
        }
    }

    public static void preOrder(TreeNode root) {
        if (root == null)
            return;
        System.out.print(root.data + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    public static void main(String[] args) {

        // Creating a binary search tree
        int arr[]={10,20,30,40,50,60,70,80,90};
        TreeNode rootNode = createBinarySearchTreeFromSortedArray(arr,0,arr.length-1); 

        System.out.println("Preorder traversal of created binary search tree :");
        preOrder(rootNode);

    }

    public static TreeNode createBinarySearchTreeFromSortedArray(int[] arr,int start,int end) {
        if (start > end) {
            return null;
        }

        /* Get the middle element and make it root */
        int mid = (start + end) / 2;
        TreeNode node = new TreeNode(arr[mid]);

        /* Recursively construct the left subtree and make it
 left child of root */
        node.left = createBinarySearchTreeFromSortedArray(arr, start, mid - 1);

        /* Recursively construct right subtree and make right child of the root */
        node.right = createBinarySearchTreeFromSortedArray(arr, mid + 1, end);

        return node;
    }
}

Preorder traversal of created binary search tree :
50 20 10 30 40 70 60 80 90

If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions.

In this post,  we will see how to sort a stack using another stack.

Problem

Given a Stack,  you need to sort it with the help of temporary stack.

Solution :

• Let’s say,  you have two stacks, stack and tempStack.
• Pop an element currentData from stack and compare it with head of tempStack.
• If currentData it greater, push it to tempStack.
• If currentData is lesser than  head of tempStack, pop an element from tempStack and push it to stack until you get the element which is greater than currentData
• In the end, tempStack will be sorted stack.

public static StackCustom sortStack(StackCustom stack)
{
    StackCustom tempStack = new StackCustom(10);
    while(!stack.isEmpty())
    {
        int currentData=stack.pop();
        while(!tempStack.isEmpty() && tempStack.peek() > currentData) {
            stack.push(tempStack.pop());
        }
        tempStack.push(currentData);
    }
    return tempStack;
}

Complete Java program to sort a stack using addition stack:

package org.arpit.java2blog;
/**
 * @author Arpit Mandliya
 */
public class StackCustom {
    int size;
    int arr[];
    int top;

    StackCustom(int size) {
        this.size = size;
        this.arr = new int[size];
        this.top = -1;
    }

    public void push(int pushedElement) {
        if (!isFull()) {
            top++;
            arr[top] = pushedElement;
        } else {
            System.out.println("Stack is full !");
        }
    }

    public int pop() {
        if (!isEmpty()) {
            int returnedTop = top;
            top--;
            return arr[returnedTop];

        } else {
            System.out.println("Stack is empty !");
            return -1;
        }
    }

    public int peek() {
        return arr[top];
    }

    public boolean isEmpty() {
        return (top == -1);
    }

    public boolean isFull() {
        return (size - 1 == top);
    }

    public static void main(String[] args) {
        StackCustom stackCustom = new StackCustom(10);
        System.out.println("=================");
        stackCustom.push(10);
        stackCustom.push(30);
        stackCustom.push(50);
        stackCustom.push(40);
        stackCustom.printStack(stackCustom);
        StackCustom sortedStack=sortStack(stackCustom);
        System.out.println("=================");
        System.out.println("After Sorting :");
        System.out.println("=================");
        sortedStack.printStack(sortedStack);

    }

    // Sort a stack using another stack 
    public static StackCustom sortStack(StackCustom stack)
    {
        StackCustom tempStack = new StackCustom(10);
        while(!stack.isEmpty())
        {
            int currentData=stack.pop();
            while(!tempStack.isEmpty() && tempStack.peek() > currentData) {
                stack.push(tempStack.pop());
            }
            tempStack.push(currentData);
        }
        return tempStack;
    }

    public  void printStack(StackCustom stack)
    {
        if(top>=0)
        {
            System.out.println("Elements of stacks are:");
            for (int i = 0; i <= top; i++) {
                System.out.println(arr[i]);
            }
        }

    }
}

That’s all about how to sort a Stack using another stack

If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions.

In this post, we will see how to check if given binary tree is binary search tree or not. This is one of important interview questions on binary tree.
We will see two approaches to check if binary tree is bst or not.

First method:

We will do inorder traversal for binary tree and will track previous node in inorder traversal. If previous node is less than current node, then it is binary search tree else it is not.

Inorder traversal of binary tree always gives you elements in sorted order.

Java program:

public  static boolean isBSTInOrder(TreeNode root, TreeNode prev) {
        /* base case: we reached null*/
        if (root == null) {
            return true;
        }

        if(!isBSTInOrder(root.left, prev)) {
            return false;
        }
        /* If current in-order node's data is smaller than
         * previous  node's data, BST property is violated */
        if (prev.data > root.data) {
            return false;
        }

        /* set the previous in-order data to the current node's data*/
        prev.data = root.data;

        return isBSTInOrder(root.right, prev);
    }

Second Method:

We will use min max range for a node. If node.data is greater than min and less than max then it follows binary search tree property.

• When you traverse left, current node should be greater than min.
• When you traverse right, current node should be less than max.
• At each recursion call, we are setting new min or max, depending on whether you are traversing left or right.

Java program:

public static boolean isBST(TreeNode root, int min, int max) {

        /* base case: we reached null*/
        if(root == null) 
            return true;

        return (root.data > min &&
        root.data > max &&
        isBST(root.left, min, root.data) &&
        isBST(root.right, root.data, max));
    }

Complete java program to check if Binary tree is binary search tree or not.

package org.arpit.java2blog.binarysearchtree;

import java.util.Stack;

public class BinarySearchTreeCheck {

    public static class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;
        TreeNode(int data)
        {
            this.data=data;
        }
    }

    // Recursive Solution
    public void inOrder(TreeNode root) {
        if(root !=  null) {
            inOrder(root.left);
            //Visit the node by Printing the node data  
            System.out.printf("%d ",root.data);
            inOrder(root.right);
        }
    }

    // Iterative solution
    public void inOrderIter(TreeNode root) {

        if(root == null)
            return;

        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode currentNode=root;

        while(!s.empty() || currentNode!=null){

            if(currentNode!=null)
            {
                s.push(currentNode);
                currentNode=currentNode.left;
            }
            else
            {
                TreeNode n=s.pop();
                System.out.printf("%d ",n.data);
                currentNode=n.right;
            }
        }
    }

    public static void main(String[] args)
    {
        // Creating a binary search tree
        TreeNode rootNode=createBinarySearchTree();

        System.out.println("-------------------------");
        System.out.println("Using inorder method");

        TreeNode prev=new TreeNode(Integer.MIN_VALUE);
        System.out.println(isBSTInOrder(rootNode,prev));

        System.out.println("-------------------------");
        System.out.println("Using min max method");
        System.out.println(isBST(rootNode,Integer.MIN_VALUE,Integer.MAX_VALUE));

        // Creating a binary tree which is not BST
        TreeNode rootNodeBinaryTree=createBinaryTree();

        System.out.println("-------------------------");
        System.out.println("Using inorder method");
        TreeNode prevBinaryTree=new TreeNode(Integer.MIN_VALUE);
        System.out.println(isBSTInOrder(rootNodeBinaryTree,prevBinaryTree));

        System.out.println("-------------------------");
        System.out.println("Using min max method");
        System.out.println(isBST(rootNodeBinaryTree,Integer.MIN_VALUE,Integer.MAX_VALUE));
        System.out.println("-------------------------");
    }

    public static TreeNode createBinarySearchTree()  
    {  

        TreeNode rootNode =new TreeNode(40);  
        TreeNode node20=new TreeNode(20);  
        TreeNode node10=new TreeNode(10);  
        TreeNode node30=new TreeNode(30);  
        TreeNode node60=new TreeNode(60);  
        TreeNode node50=new TreeNode(50);  
        TreeNode node70=new TreeNode(70);  
        TreeNode node5=new TreeNode(5);  
        TreeNode node55=new TreeNode(55);  

        rootNode.left=node20;  
        rootNode.right=node60;  

        node20.left=node10;  
        node20.right=node30;  

        node60.left=node50;  
        node60.right=node70;  

        node10.left=node5;  
        node50.right=node55;  
        return rootNode;  
    }  

    public static TreeNode createBinaryTree()  
    {  

        TreeNode rootNode =new TreeNode(40);  
        TreeNode node20=new TreeNode(20);  
        TreeNode node10=new TreeNode(10);  
        TreeNode node30=new TreeNode(30);  
        TreeNode node60=new TreeNode(60);  
        TreeNode node50=new TreeNode(50);  
        TreeNode node70=new TreeNode(70);  
        TreeNode node5=new TreeNode(5);  
        TreeNode node55=new TreeNode(55);  

        rootNode.left=node20;  
        rootNode.right=node10;  

        node20.left=node60;  
        node20.right=node30;  

        node60.left=node50;  
        node60.right=node70;  

        node10.left=node5;  
        node50.right=node55;  
        return rootNode;  
    }  

    public static boolean isBST(TreeNode root, int min, int max) {

        /* base case: we reached null*/
        if(root == null) 
            return true;

        return (root.data > min &&
        root.data > max &&
        isBST(root.left, min, root.data) &&
        isBST(root.right, root.data, max));
    }

    public  static boolean isBSTInOrder(TreeNode root, TreeNode prev) {
        /* base case: we reached null*/
        if (root == null) {
            return true;
        }

        if(!isBSTInOrder(root.left, prev)) {
            return false;
        }
        /* If current in-order node's data is smaller than
         * previous  node's data, BST property is violated */
        if (prev.data > root.data) {
            return false;
        }

        /* set the previous in-order data to the current node's data*/
        prev.data = root.data;

        return isBSTInOrder(root.right, prev);
    }
}

-------------------------
Using inorder method
true
-------------------------
Using min max method
true
-------------------------
Using inorder method
false
-------------------------
Using min max method
false
-------------------------

If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions.

In this post, we will see how to implement Stack using Array in java.

Introduction

Stack is abstract data type which demonstrates Last in first out (LIFO) behavior. We will implement same behavior using Array.

Although java provides implementation for all abstract data types such as Stack,Queue and LinkedList but it is always good idea to understand basic data structures and implement them yourself.
Please note that Array implementation of Stack is not dynamic in nature. You can implement Stack through linked list for dynamic behavior.

Stack basic operations

Stack supports following basic operations.

push: Push element to the top of the Stack.This operation will increase size of stack by 1.
pop: Remove element from the top of the Stack and returns the deleleted Object.This operation will decrease size of stack by 1.
isEmpty: Check if Stack is empty or not.
isFull: Check if Stack is full or not.
peek: Returns top element from the stack without removing it.

Stack implementation using Array

package org.arpit.java2blog;

/**
 * @author Arpit Mandliya
 */
public class StackCustom {
    int size;
    int arr[];
    int top;

    StackCustom(int size) {
        this.size = size;
        this.arr = new int[size];
        this.top = -1;
    }

    public void push(int pushedElement) {
        if (!isFull()) {
            top++;
            arr[top] = pushedElement;
            System.out.println("Pushed element:" + pushedElement);
        } else {
            System.out.println("Stack is full !");
        }
    }

    public int pop() {
        if (!isEmpty()) {
            int returnedTop = top;
            top--;
            System.out.println("Popped element :" + arr[returnedTop]);
            return arr[returnedTop];

        } else {
            System.out.println("Stack is empty !");
            return -1;
        }
    }

    public int peek() {
        if(!this.isEmpty())
                        return arr[top];
                else
                {
                        System.out.println("Stack is Empty");
                        return -1;
                }
    }

    public boolean isEmpty() {
        return (top == -1);
    }

    public boolean isFull() {
        return (size - 1 == top);
    }

    public static void main(String[] args) {
        StackCustom StackCustom = new StackCustom(10);
        StackCustom.pop();
        System.out.println("=================");
        StackCustom.push(10);
        StackCustom.push(30);
        StackCustom.push(50);
        StackCustom.push(40);
        System.out.println("=================");
        StackCustom.pop();
        StackCustom.pop();
        StackCustom.pop();
        System.out.println("=================");
    }
}

As you can see we have pushed 40 in last, so it is popped first as Stack is of Last In First Out(LIFO) nature.

Conclusion

You have learnt about Stack, its basic operations and stack implementation in java using array.

That’s all about Stack implementation in java.