# 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 Breadth first traversal and Depth First traversal. Tree is a special kind of Graph in which Breadth first traversal and Depth First traversal is divided as follows,

1. Level Order Traversal
2. Depth First Traversal
1. Preorder traversal
2. Inorder traversal
3. Postorder 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.

Approach 2: Level Order Traversal

If we know how to print all nodes at given level, then we can just find the height of the tree first and loop through the height of tree calling printAllNodesAtGivenLevel(i) where i goes from 0 to height of tree.

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.

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.Queue;

public class BinaryTreeTraversal {
private Node rootNode;

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

public BinaryTreeTraversal(){

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;

while(!queue.isEmpty()){
Node obj = (Node)queue.poll();

System.out.print(obj.getData() + " ");

if(obj.getLeft()!=null)

if(obj.getRight()!=null)
}
}

//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{
}
}

private void addNodeInProperPlace(Node rootNode, int data){
if(data>rootNode.getData()){
if(rootNode.getRight()!=null){
}else{
Node temp1 = new Node(data);
rootNode.setRight(temp1);
}
}else if(data<rootNode.getData()){
if(rootNode.getLeft()!=null){
}else{
Node temp1 = new Node(data);
rootNode.setLeft(temp1);
}
}
}

}

```

### You may also like to see

#### Boundary Traversal of binary tree.

Enjoy !!!!

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