Binary Tree Traversals - Inorder, Preorder, Postorder, Levelorder

What is Binary Tree Traversal?


From Wiki: 
In computer science, Graph traversal is the problem of visiting all the nodes of 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 Search Tree sample:


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,
Breadth First Traversal


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. 

Levelorder 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

For reading a Tree Level by Level, we require Queue to store the Nodes.

Algorithm:
1.  Put a Root Node in a Queue.
2.  Iterate till the Queue is not Empty.
3.  While iterating, take one element from Queue say 45 in our example, print it and put children's of
     45 in queue.
4.  Repeat steps till Queue is not empty.

Depth First Traversal

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, 

1. Preorder Traversal. 
2. Postorder Traversal. 
2. Inorder Traversal. 

Preorder 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 

Inorder 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 

Postorder 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 

Java Program for Binary Tree Traversals.



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

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

 public int getData() {
  return data;
 }
 public void setData(int data) {
  this.data = data;
 }
 public Node getLeft() {
  return left;
 }
 public void setLeft(Node left) {
  this.left = left;
 }
 public Node getRight() {
  return right;
 }
 public void setRight(Node right) {
  this.right = right;
 }
} 

BinaryTreeTraversal.java

package tree;

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTreeTraversal {
 private Node rootNode;

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

 public BinaryTreeTraversal(){

  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);
 }
 
 //Levelorder 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());
  }
 }

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

 //Postorder 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);
   }
  }
 }
 
}

You may also like to see


Print Nodes in Top View of Binary Tree

Print Nodes in Bottom View of Binary Tree.

Print a Binary Tree in Vertical Order

Zig Zag Traversal of Binary Tree. 

Boundary Traversal of binary tree. 

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.

Post a Comment