Binary Tree Traversal (In-Order, Pre-Order, Post-Order, Level-Order).

package tree;
import java.util.LinkedList;
import java.util.Queue;

/* 
 From Wiki: 
 In computer science, graph traversal is the problem of visiting all the nodes in a graph in a particular manner, 
 updating and/or checking their values along the way. 
 Tree traversal is a special case of graph traversal.
 
  Binary Tree sample:
 
                  45
                  /\ 
                 /  \
                25   75
                /\    
              15  35    

 There are 2 types of Graph traversal algorithms,
 1. Breadth First Traversal
 2. Depth First Traversal
 
 Tree is a special kind of Graph, where above 2 traversal means,
 1. Breadth First Traversal is a traversing way where child at same levels are read first before visiting their child.
  Which is nothing but a LEVEL-ORDER Traversal.
 
  Level order traversal: 
  To traverse a binary tree in Level order, following operations are carried-out 
  (a) Visit the nodes of tree Level by level (ie, from left to right, level by level).  
  (b) Here every Node of same Level is visited first before going to a lower levels. 
  Therefore, the Levelorder traversal of the above sample tree will outputs:
  45 25 75 15 35

 2. Depth First Traversal is a traversing way where all the children of Left node are read first and then all the children of right node 
  that is once we start visiting a Left node, we cannot visit right node until and unless all child of left node are not visited.
  This way of reading leads to 3 ways of Traversal,
  2.1. Pre Order Traversal.
  2.2. Post Order Traversal.
  2.3. In Order Traversal.
     
 Pre order traversal: 
  To traverse a binary tree in Preorder, following operations are carried-out 
  (a) Visit the root node and print data of that node.
  (b) Traverse the left subtree, and 
  (c) Traverse the right subtree.
  Therefore, the Preorder traversal of the above sample tree will output:
  45 25 15 35 75
  
  In-order traversal: 
   To traverse a binary tree in Inorder, following operations are carried-out 
   (a) Traverse the left subtree,
   (b) Visit the root node and print data of that node, and 
   (c) Traverse the right subtree.
  Therefore, the Inorder traversal of the above sample tree will output:
  15 25 35 45 75

 Post order traversal: 
  To traverse a binary tree in Postorder, following operations are carried-out 
  (a) Traverse the left subtree, 
  (b) Traverse the right subtree, and
  (c) Visit the root node and print data of that node.
  Therefore, the Postorder traversal of the above sample tree will output:
  15 35 25 75 45
 */

public class BinarySearchTreeTraversal {
 private Node rootNode;

 public static void main(String[] args) {
  new BinarySearchTreeTraversal();
 }

 public BinarySearchTreeTraversal(){

  addNode(rootNode, 45); 
  addNode(rootNode, 25); 
  addNode(rootNode, 75); 
  addNode(rootNode, 15); 
  addNode(rootNode, 35); 
  
  System.out.println("In Order Traversal :");
  printTreeInOrder(rootNode);
  
  System.out.println("\nPre Order Traversal :");
  printTreePreOrder(rootNode);
  
  System.out.println("\nPost Order Traversal :");
  printTreePostOrder(rootNode);
  
  System.out.println("\nLevel Order Traversal :");
  printTreeLevelOrder(rootNode);
 }
 
 //Level Order Printing.
 private void printTreeLevelOrder(Node rootNode){
  if(rootNode==null)
   return;

  Queue<Node> queue = new LinkedList<Node>();
  queue.add(rootNode);
  
  while(!queue.isEmpty()){
   Node obj = (Node)queue.poll();
   System.out.print(obj.getData() + " ");
   if(obj.getLeft()!=null)
    queue.add(obj.getLeft());
    
   if(obj.getRight()!=null)
    queue.add(obj.getRight());
  }
 }

 //In Order Printing.
 private void printTreeInOrder(Node rootNode){
  if(rootNode==null)
   return;
  printTreeInOrder(rootNode.getLeft());
  System.out.print(rootNode.getData() + " ");
  printTreeInOrder(rootNode.getRight());
 }
 
 //Pre Order Printing. 
 private void printTreePreOrder(Node rootNode){
  if(rootNode==null)
   return;
  System.out.print(rootNode.getData() + " ");
  printTreePreOrder(rootNode.getLeft());
  printTreePreOrder(rootNode.getRight());
 }

 //Post Order Printing.
 private void printTreePostOrder(Node rootNode){
  if(rootNode==null)
   return;
  printTreePostOrder(rootNode.getLeft());
  printTreePostOrder(rootNode.getRight());
  System.out.print(rootNode.getData() + " ");
 }
  
 private void addNode(Node rootNode, int data){
  if(rootNode==null){
   Node temp1 = new Node(data);
   this.rootNode=temp1;
  }else{
   addNodeInProperPlace(rootNode, data);
  }
 }
 
 private void addNodeInProperPlace(Node rootNode, int data){ 
  if(data>rootNode.getData()){
   if(rootNode.getRight()!=null){
    addNode(rootNode.getRight(), data);
   }else{
    Node temp1 = new Node(data);
    rootNode.setRight(temp1);
   }
  }else if(data<rootNode.getData()){
   if(rootNode.getLeft()!=null){
    addNode(rootNode.getLeft(), data);
   }else{
    Node temp1 = new Node(data);
    rootNode.setLeft(temp1);
   }
  }
 }
 
}