Spiral/Zigzag Level order traversal of Binary Tree in Java

Zigzag Traversal of Binary Tree

How to traverse Binary Tree to print out Zigzag.

This is one of popular interview question of Data structure written in Java to accomplish to zigzag layout.

Here, We create a Node having left and right node that point to backward and forward Node.

There are three way to traverse Tree :- 

• In-Order -
• Traverse from root
• then, left
• then, right
• Pre-Order - 
• Traverse from left
• then, root node
• then right node
• Post-Order -
• Traverse from left
• then right
• then left

Below are Algorithm and Java Code for traversing methods:
 Inorder :-

inorder(node)
  if node == null then return
  inorder(node.left)
  visit(node)
  inorder(node.right)

Code : -

public static void inOrderTraverse(Node root){
  if(root != null){
   System.out.printf("%d ",root.data);
   inOrderTraverse(root.left);
   inOrderTraverse(root.right);
   
  }
  
 }

preOrder :-

  preorder(node)
  if node == null then return
  visit(node)
  preorder(node.left) 
  preorder(node.right)

Code :-

public static void preOrderTraverse(Node root){
  if(root != null){
   preOrderTraverse(root.left);
   System.out.printf("%d ",root.data);
   preOrderTraverse(root.right);
   
  }
  
 }

postOrder :-

postorder(node)
  if node == null then return
  postorder(node.left)
  postorder(node.right)
  visit(node)

Code -

public static void postOrderTraverse(Node root){
  if(root != null){
   postOrderTraverse(root.left);
   postOrderTraverse(root.right);
   System.out.printf("%d ",root.data);
   
  }
  
 }

We assume that below is our tree-

class Node {
 Node left;
 Node right;
 int data;

 Node(int value) {
  this.data = value;
 }
}

Here, Implementation of ZigZag using two stack:-

 public static void printZigZagTree(Node root) {
  Stack stack = new Stack();
  stack.push(root);
  boolean flags = false;
  while (!stack.isEmpty()) {
   Stack tempStack = new Stack();
   while (!stack.isEmpty()) {
    Node node = stack.pop();
    System.out.println(node.data);
    if (!flags) {
     if (node.right != null) {
      tempStack.push(node.right);
     }
     if (node.left != null) {
      tempStack.push(node.left);
     }
    } else {
     if (node.left != null) {
      tempStack.push(node.left);
     }
     if (node.right != null) {
      tempStack.push(node.right);
     }
     
    }
   }
   flags = !flags;
   stack = tempStack;
  }

 }

Below are complete code:- 

package com.DS;

import java.util.Stack;


class Node {
 Node left;
 Node right;
 int data;

 Node(int value) {
  this.data = value;
 }
}

/**
 * @author ajay kumar gupta
 *
 */
public class ZigZagDB {

 public static void main(String args[]) {
  Node root = getTreeRoot();
  System.out.println("ZigZag Traverse :- ");
  printZigZagTree(root);
  System.out.println("\n InOrder Traverse :- ");
  inOrderTraverse(root);
  System.out.println("\n PreOrder Traverse :- ");
  preOrderTraverse(root);
  System.out.println("\n PostOrder Traverse :- ");
  postOrderTraverse(root);
 }
 

 public static void inOrderTraverse(Node root){
  if(root != null){
   System.out.printf("%d ",root.data);
   inOrderTraverse(root.left);
   inOrderTraverse(root.right);
   
  }
  
 }
 
 public static void preOrderTraverse(Node root){
  if(root != null){
   preOrderTraverse(root.left);
   System.out.printf("%d ",root.data);
   preOrderTraverse(root.right);
   
  }
  
 }
 
 public static void postOrderTraverse(Node root){
  if(root != null){
   postOrderTraverse(root.left);
   postOrderTraverse(root.right);
   System.out.printf("%d ",root.data);
   
  }
  
 }
 public static void printZigZagTree(Node root) {
  Stack stack = new Stack();
  stack.push(root);
  boolean flags = false;
  while (!stack.isEmpty()) {
   Stack tempStack = new Stack();
   while (!stack.isEmpty()) {
    Node node = stack.pop();
    System.out.printf("%d ",node.data);
    if (!flags) {
     if (node.right != null) {
      tempStack.push(node.right);
     }
     if (node.left != null) {
      tempStack.push(node.left);
     }
    } else {
     if (node.left != null) {
      tempStack.push(node.left);
     }
     if (node.right != null) {
      tempStack.push(node.right);
     }
     
    }
   }
   flags = !flags;
   stack = tempStack;
  }

 }

 public static Node getTreeRoot() {
  Node root10 = new Node(10);
  Node node20 = new Node(20);
  Node node30 = new Node(30);
  Node node40 = new Node(40);
  Node node50 = new Node(50);
  Node node60 = new Node(60);
  Node node70 = new Node(70);
  Node node80 = new Node(80);
  Node node90 = new Node(90);
  Node node95 = new Node(95);
  Node node65 = new Node(65);
  Node node55 = new Node(55);
  Node node66 = new Node(66);
  Node node35 = new Node(35);
  Node node45 = new Node(45);

  root10.right = node30;
  root10.left = node20;

  node20.right = node60;
  node20.left = node70;

  node30.right = node40;
  node30.left = node50;

  node70.right = node90;
  node70.left = node80;

  node60.right = node65;
  node60.left = node95;

  node50.right = node66;
  node50.left = node55;

  node40.right = node45;
  node40.left = node35;

  return root10;
 }

}

output :-

10 20 30 40 50 60 70 80 90 95 65 55 66 35 45  

How to detect a loop in a linked list

 

How to implement Single Link list is Circular ?

Here, We have implemented a Single linked list with insert,traverse, before/after insert and circular check.

Method implemented in this snippet : -

•  insert(Node node) :  Insert Node into Linkedlist
• insert(int value) : insert value into linkedlist
• insertAfter(Node node,int newValue) : Insert value after given node  ( node ).
• insertBefore(Node node,int newValue) : Insert value before given node (node) .
• getNode(int value) : retrive Node Object by given value
• isCycle() : check Linked list is Cycle or not , return boolean value
  
  
  
  

Complete code here :-

class Node {
 public Node next;
 public int data;

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

/**
 * @author ajay kumar gupta
 *
 */
public class CycleLinkedList {

 Node head;

 public CycleLinkedList() {
 }

 public void insert(Node node) {
  Node current = head;
  if (current == null) {
   head = node;
  } else {
   while (current.next != null) {
    current = current.next;
   }
   current.next = node;
  }
 }

 /**
  * @param node
  * @param newValue
  * After which Node, new value will be store
  */
 public void insertAfter(Node node, int newValue) {
  Node current = head;
  Node newNode = new Node(newValue);
  if (current == null) {
   head = newNode;
  } else {
   while (current != node) {
    current = current.next;
   }
   newNode.next = node.next;
   current.next = newNode;
  }
 }
 // 10 20 30 40 50 60

 /**
  * @param node
  * @param newValue
  * Before which Node, new value will be store
  */
 public void insertBefore(Node node, int newValue) {
  Node current = head;
  Node newNode = new Node(newValue);
  if (current == null) {
   head = newNode;
  } else {
   while (current.next != node) {
    current = current.next;
   }
   newNode.next = node;
   current.next = newNode;
  }
 }
 public Node getNode(int data) {

  Node current = head;
  if (current.data == data) {
   return current;
  }
  while (current.next != null) {
   current = current.next;
   if (current.data == data) {
    return current;
   }
  }
  return null;
 }

 public void insert(int data) {
  if (head == null) {
   head = new Node(data);
  } else {
   Node current = head;
   while (current.next != null) {
    current = current.next;
    System.out.println(current.data + " == " + head.data);
   }
   current.next = new Node(data);
  }
 }

 /*
  * To check list is cycle, we keep two pointer i.e fast and slow, each one
  * started from head node, fast node point to node ahead to next node while slow node 
  * point to just next node. Both pointer will be running until fast and slow get equals. 
  * example :
  * 
  * List is : 10 20 30 40 50 60 
  * 
  * Head node is 10. fast node point to Node(30) initially and subsequently increment by two node 
  * but slow node point
  * to Node(20) initially and subsequently increment by one next node.
  *  
  * fast | slow
  * 30  |  20
  * 50 |  30
  * 60 |  40
  * 20 |  50
  * 40 |  90
  * 90 |  60
  * 10 |  10 // Wow match here... 
  */
 public boolean isCycle() {
  Node fast = head;
  Node slow = head;
  while (fast != null && fast.next != null) {
   fast = fast.next.next;
   slow = slow.next;
   if (fast == slow) {
    return true;
   }

  }
  return false;
 }

 public void traverse() {
  Node current = head;
  while (current != null && current.next != null) {
   current = current.next;
   System.out.printf("%d ",current.data);
  }
 }

 public static void main(String args[]) {
  CycleLinkedList c = new CycleLinkedList();
  
  Node n1=new Node(10);
  Node n2=new Node(20);
  Node n3=new Node(30);
  Node n4=new Node(40);
  Node n5=new Node(50);
  Node n6=new Node(60);
  
  c.insert(n1);
  c.insert(n2);
  c.insert(n3);
  c.insert(n4);
  c.insert(n5);
  c.insert(n6);
  // traverse CycleLinkedLink here
  c.traverse(); // 20 30 40 50 60
  System.out.println("Add New Value after n Node ");
  c.insertAfter(n5,90); // output 20 30 40 50 90 60
  c.traverse();
  
  System.out.println("Add New Value before n Node ");
  c.insertBefore(n4,100);
  c.traverse(); // output 20 30 100 40 50 90 60
  
  System.out.println(c.isCycle()); // false
  // Again, Traverse here...
  c.traverse();
  // Making CycleLinkedLink Cycle by point last next node to n1 node.
  System.out.println(" Make Cycle Linke list.");
  c.insert(n1);
  System.out.println(c.isCycle()); // true
  
  
  
 }

}

ATM Cashwithdraw Problem and Solved

Problem statements here :-

• ATM dispenses amount base on user enter amount.
• Amount must be multiple of 50 
• Should be parallel withdraw system, multiple user can withdraw amount at same time.
• Availability of various Denominator in ATM i.e 50,100,500,1000.

ATMMachine Java file :

package com.atm;

import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.TreeMap;
import java.util.TreeSet;

public class ATMMachine {

    private final Map<Integer, Integer> denominatorMap;

    public ATMMachine(Map<Integer, Integer> denoMap) {
        this.denominatorMap = denoMap;
    }

    private boolean isValidAmt(int amt) {
        return amt % 50 == 0 ? true : false;
    }

    private int getDenominatorNotes(int denominator) {
        return denominatorMap.get(denominator);
    }

    public synchronized Map<Integer, Integer> withDrawAmt(int amt) {
        if (!isValidAmt(amt)) {
            System.out.println(" Please enter amount multiple by 50 only.");
        }
        Map<Integer, Integer> returnMap = new TreeMap<Integer, Integer>();
        Iterator<Integer> iteratorOfDenominator = new TreeSet<Integer>(
                denominatorMap.keySet()).descendingIterator();
        while (amt > 0) {
            Integer denominator =0;
            try{
            denominator = iteratorOfDenominator.next();
            }catch(NoSuchElementException e){
                System.out.println(" Please enter another amount multiple by 100");
                break;
            }
            Integer noOfNotes = amt < denominator ? 0 : amt / denominator;
            if (noOfNotes > getDenominatorNotes(denominator)) {
                noOfNotes = getDenominatorNotes(denominator);
            }
            /*System.out.printf(" amt %d denominator %d NoOfNotes %d\n", amt,
                    denominator, noOfNotes);
            */
            amt = amt - (denominator * noOfNotes);
            returnMap.put(denominator, noOfNotes);
            reduceBalance(denominator, noOfNotes);
        }
        return returnMap;
    }

    public String printWithDrawAmtWithDenominator(
            Map<Integer, Integer> returnMap) {

        StringBuffer sb = new StringBuffer();
        for (Integer denominator : returnMap.keySet()) {
            sb.append("").append(denominator).append(" * ")
                    .append(returnMap.get(denominator)).append(" = ")
                    .append(denominator * returnMap.get(denominator))
                    .append(",\n");
        }
        return sb.toString();
    }

    private synchronized void reduceBalance(int denominator, int amt) {
        Integer _denominator_amt = denominatorMap.get(denominator);
        denominatorMap.put(denominator, (_denominator_amt - amt));
    }

    public synchronized int getBalanceATMAmt() {
        int balance = 0;
        for (Integer denominator : denominatorMap.keySet()) {
            balance += (denominator * denominatorMap.get(denominator));
        }
        return balance;
    }

} 
 ATMUser Java file :

package com.atm;

public class ATMUser implements Runnable{

    private final ATMMachine machine;
    private final int amt;
    public ATMUser(ATMMachine machine,int amount){
        this.machine = machine;
        this.amt = amount;
    }
   
    @Override
    public void run() {
        System.out.println(" Request Amount is :"+this.amt);
        System.out.println(" Total Amount Balance Before withdraw "+machine.getBalanceATMAmt());
        System.out.println(" Receive Amount From ATM :"+machine.printWithDrawAmtWithDenominator(machine.withDrawAmt(this.amt)));
        System.out.println(" Total Amount Balance Before withdraw "+machine.getBalanceATMAmt());
    }

}


Main Java Program :-

package com.atm;

import java.util.HashMap;
import java.util.Map;

public class Main {

   
    public static void main(String args[]){
       
        ATMMachine machine = new ATMMachine(depositeAmtToATM());
       
        ATMUser user1 = new ATMUser(machine, 54050);
       
        Thread t1 = new Thread(user1);
        t1.start();
       
    }
   
    private static Map<Integer,Integer> depositeAmtToATM(){
        Map<Integer,Integer> ATMDenominator = new HashMap<Integer, Integer>();
        ATMDenominator.put(1000,120);
        ATMDenominator.put(500,220);
        ATMDenominator.put(100,500);
        ATMDenominator.put(50,10);
        return ATMDenominator;
    }
}


Please write here your suggestion... thanks

Concurrent Programming : Semaphore

What is Semaphores ?

A semaphore is a counter that controls the access to one or more shared resources. This mechanism is one of the basic tools of concurrent programming and is provided by most of the programming languages.

The concept of a semaphore was introduced by Edsger Dijkstra in 1965 and was used for the first time in the THEOS operating system

Example:-  Suppose there are three shared printer in your workspace and for each print request printer do printing. Question come here how shared resources has been access control over concurrent request, solution is “Semaphores”.

Semaphores has set of permit that access control over shared resources.  In our example there are three shared printer so we set three permit on semaphore, subsequently every access to shared resources semaphore decrement it values by one until values is greater than zero. Once it’s values is zero, Means all shared resources are busy and no more permit will be allowed until any resources is free. All requesting print commands will wait for release the resources.

Important Methods :

  Constructor :

• Semaphore(int permits) :Creates a Semaphore with the given number of permits and nonfair fairness setting.
• Semaphore(int permits, boolean fair) : -Creates a Semaphore with the given number of  permits and the given fairness setting

 Acquire() :-  Acquires a permit from this semaphore, blocking until one is available, or the thread is   interrupted.

 Release() :-  Releases a permit or increment permit by one, returning it to the semaphore.

Key Points:- 

     By default Fairness properties is false; means this class make no guarantees about the order in   which thread acquire permits.

  

Coding practices here : -

How to write custom JDBC Connection Pool in java

Here have another interview programming solved question that give you pretty good idea to solve such kind of cases. below section we created a Connection pool that hold 10 connection instance to give the connection object to different different context. Typically, pool is basically a set of data that belong to same type like Connection Pool,String pool. effectively it increase the performance of system.

Interview question to write a custom Connection pool to prevent costly creation of connection object every time.

As below example i will demonstrate how we can achieve it in java language...

Create a configuration java file that contains all configuration related setup of Database..


package com.connection.pool;

public class Configuration {
    public String DB_USER_NAME;
    public String DB_PASSWORD;
    public String DB_URL;
    public String DB_DRIVER;
    public int DB_MAX_CONNECTIONS;

    private Configuration(){
        init();
    }
   
    private static Configuration config = new Configuration();
    public static  Configuration getInstance(){
        return config;
    }
   
    private void init() {
          DB_USER_NAME = "root";
          DB_PASSWORD = "root";
          DB_URL = "jdbc:mysql://localhost:3306/test";
          DB_DRIVER = "com.mysql.jdbc.Driver";
          DB_MAX_CONNECTIONS = 5; // Maximun nos of Connection in Pool
         }
}


Create a ConnectionPool java file contains all logic to create a connection...

package com.connection.pool;

import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.SQLException;
import java.util.ArrayList;
import java.util.List;

public class JdbcConnectionPool {

    private List<Connection> connectionPool = new ArrayList<Connection>();
    private Configuration config = Configuration.getInstance();

    public JdbcConnectionPool(){
        try {
            initilizeConnectionPool();
            System.out.println(" Default Pool Size is "+connectionPool.size());
        } catch (ClassNotFoundException e) {
            e.printStackTrace();
        } catch (SQLException e) {
            e.printStackTrace();
        }
    }
    private void initilizeConnectionPool() throws ClassNotFoundException, SQLException {
        while(!isConnectionPoolFull()){
            connectionPool.add(getNewConnection());
        }
    }

    private synchronized boolean isConnectionPoolFull() {
        if (connectionPool.size() > config.DB_MAX_CONNECTIONS) {
            return true;
        }
        return false;
    }
   
    public synchronized Connection getConnectionPool(){
        Connection connection = null;   
        if(connectionPool.size() >0 ){
            connection =  connectionPool.get(0);
            connectionPool.remove(0);
        }
        return connection;
    }

    private Connection getNewConnection() throws SQLException,
            ClassNotFoundException {
        Class.forName(config.DB_DRIVER);
        Connection connection = DriverManager.getConnection(config.DB_URL,
                config.DB_USER_NAME, config.DB_PASSWORD);
        return connection;
    }
}
 
End here...