Tree Traversal

Unlike the linear data structures(like array, linked list), Tree can be traversed in different ways.
Following are the ways for traversing the Tree.
1. Pre-order Traversal
2. Post-order Traversal
3. In-order Traversal
4. Level Order Traversal

1. Pre-order Traversal:
       In this traversal, first we visit the current node, then left sub tree and then right sub tree.
       In order to illustrate the pre-order traversal, let us consider the below binary tree: 
   

          Algorithm:
                PreOrder(TreeNode root)                             
if root is null Then return                          

Visit the root                                          
PreOrder(root.left)                                 
PreOrder(root.right)                               

 2. Post-order Traversal:
       In this traversal, first we traverse the left sub tree, then right sub tree and then current node.
       In order to illustrate the post-order traversal, let us consider the below binary tree: 

 
            Algorithm:
                PostOrder(TreeNode root)
if root is null Then return

PostOrder(root.left)
PostOrder(root.right)
                    Visit the root

3. In-order Traversal:
        In this traversal, first we traverse left sub tree then current node and then right sub tree.
        In order to illustrate the in-order traversal, let us consider the below binary tree: 
     

         Algorithm:
                inorder(TreeNode root)
if root is null Then return

inorder(root.left)
                    Visit the root
inorder(root.right)
                 

Implementation:

class MirrorOfBinaryTree{
//Tree structure
static class Tree{
int data;
Tree left = null;
Tree right = null;

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

//Utility to create the tree
public static Tree createBST(int []a, int left, int right){
if(right < left)
return null;

int mid = (left + right)/2;
Tree root = new Tree(a[mid]);
root.left = createBST(a, left, mid - 1);
root.right = createBST(a, mid + 1, right);

return root;
}

//Pre-order traversal
public static void preOrder(Tree root){                              
if(root != null){                                                              
System.out.print(root.data+" ");  //Visit the root       
preOrder(root.left);  //Traverse the left sub tree      
preOrder(root.right); //Traverse the right sub tree  
}                                                                                   
}                                                                                          

              public static void inOrder(Tree root){          
                        if(root != null){                                       
                           inOrder(root.left);                            
                           System.out.print(root.data+" ");       
                           inOrder(root.right);                          
                       }                                                             
              }                                                                    


             public static void postOrder(Tree root){        
                     if(root != null){                                         
  postOrder(root.left);                           
postOrder(root.right);                         
System.out.print(root.data+" ");          
                     }                                                              
            }                                                                    

}

public static void main(String []args){
int []a = {1,2,3,4,5,6,7};

Tree root = Tree.createBST(a , 0, a.length - 1);   //create the tree
Tree.preOrder(root);
}
}