## Tree Traversal

A Tree can be traversed in the following `standard depth first` ways

1. Pre Order
2. In Order
3. Post Order

#### Tree Node

Following is the Treenode class that represent the Node in a Tree

``````package com.ekiras.ds.base;

public class TreeNode {

public int data;
public TreeNode left;
public TreeNode right;

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

@Override
public String toString() {
return "TreeNode{" +
"data=" + data +
", left=" + left +
", right=" + right +
'}';
}
}

``````

### InOrder Traversal

Inorder traversal means that for every node,

1. First the left sub-tree of the node is traversed
2. then the root node is traversed
3. and at last the right node/ right sub-tree
``````                1
/ \
2   3
/  \   \
4    5   6
``````

For inorder traversal, we need to traverse the left sub tree first, so node `1`’s left sub-tree is traversed before node `1` itself. Node `2` is left of `1` and similarly for node `2`, node `4` is the left node. So first node in traversal will be `4` then `2` and then node `5`. Now we have traversed the left sub tree of the root node `1`, now we will print `1` and then traverse right sub tree of root node `1`.

So the final output will be as follows

``````4 2 5 1 3 6
``````

#### Program

``````package com.ekiras.ds.trees.traversal;

import com.ekiras.ds.base.TreeNode;

public class InOrderTreeTraversal {

public static void main(String[] args) {
TreeNode node = new TreeNode(1);
node.left = new TreeNode(2);
node.left.left = new TreeNode(4);
node.left.right = new TreeNode(5);
node.right = new TreeNode(3);
node.right.right = new TreeNode(6);

inOrder(node);
}

private static void inOrder(TreeNode node)
{
if(node==null)
return;
System.out.print(node.data+" ");
inOrder(node.left);
inOrder(node.right);
}
}
``````

### PreOrder Traversal

PreOrder traversal means that for every node,

1. First the node itself is traversed
2. then the left sub-tree is traversed
3. and at last the right sub-tree is traversed
``````                1
/ \
2   3
/  \   \
4    5   6
``````

For the above tree, root node 1 is traversed first, then we go to the left child of the root node that is `2` then to the left node of `2` that is `4`. Since `4` has no child nodes, we go back to node `2` and traverse its right node that is `5`. Now all the left nodes of root node have been traversed, so we will now traverse right sub-tree of `1`. So the traversal of above tree will give the following output

``````1 2 4 5 3 6
``````

#### Program

``````package com.ekiras.ds.trees.traversal;

import com.ekiras.ds.base.TreeNode;

public class PreOrderTreeTraversal {

public static void main(String[] args) {
TreeNode node = new TreeNode(1);
node.left = new TreeNode(2);
node.left.left = new TreeNode(4);
node.left.right = new TreeNode(5);
node.right = new TreeNode(3);
node.right.right = new TreeNode(6);

preOrder(node);
}

private static void preOrder(TreeNode node)
{
if(node==null)
return;
preOrder(node.left);
System.out.print(node.data+" ");
preOrder(node.right);
}

}
``````

### PostOrder Traversal

PostOrder traversal means that for every node,

1. First the left sub-tree of the node is traversed
2. then the right sub-tree of the root is traversed
3. and at last the root node is traversed.
``````                1
/ \
2   3
/  \   \
4    5   6
``````

For the above tree, first the left sub tree of root node `1` is traversed, so we visit node `2`, then we visit left sub tree of node `2` that is `4`. Since node `4` has no child nodes we print `4`. Now right sub-tree of node `2` is traversed that is `5`. After both left and right sub tree of node `2` is traversed we print node `2`. Now we traverse right sub tree of node `1`, that is node `3`. Node `3` has no left child but has a right child so node `6` will be printed first and then node `3` and finally node `1`.

``````4 5 2 6 3 1
``````

#### Program

``````package com.ekiras.ds.trees.traversal;

import com.ekiras.ds.base.TreeNode;

public class PostOrderTreeTraversal {

public static void main(String[] args) {
TreeNode node = new TreeNode(1);
node.left = new TreeNode(2);
node.left.left = new TreeNode(4);
node.left.right = new TreeNode(5);
node.right = new TreeNode(3);
node.right.right = new TreeNode(6);

postOrder(node);
}

private static void postOrder(TreeNode node)
{
if(node==null)
return;
postOrder(node.left);
postOrder(node.right);
System.out.print(node.data+" ");
}
}
``````