Tree Traversal : Inorder Preorder Postorder in Java

Tree Traversal : Inorder Preorder Postorder

In linear data structures like arrays and linked lists, we could traversel in one way but in tree data structures like binary tree, we can do tree traverse them in different ways. In this article we will learn about inorder, preorder and postorder traversal.

Tree Traversal : inorder, preorder, postorder in java

Example

Example of Tree Traversal in java

Different Tree Traversal Algorithms

Algorithm to Find Inorder Traversal

 Algorithm inorder(tree)

  1.   Recursively traverse left subtree.
  2.   Visit root node.
  3.   Recursively traverse right subtree.

Algorithm to find preorder traversal

Algorithm  preorder(Tree):

  1. Visit root node.
  2. Recursively traverse left subtree.
  3. Recursively traverse right subtree.

Algorithm to find Postorder traversal

Algorihtm postorder(Tree):

  1. Recursively traverse left sub-tree.
  2. Recursively traverse right sub-tree.
  3. Visit root node.

Code in Java

class Node {
int key;
Node left, right;

public Node(int item)
{
key = item;
left = right = null;
}
}

class BinaryTree {
// Root of Binary Tree
Node root;

BinaryTree() {
root = null;
}

void postorder(Node ptr)
{
if (ptr == null)
return;

// first recur on left subtree
postorder(ptr.left);

// then recur on right subtree
postorder(ptr.right);

// now deal with the node
System.out.print(ptr.key + " ");
}

/* Given a binary tree, print its nodes in inorder*/
void inorder(Node ptr)
{
if (ptr == null)
return;

/* first recur on left child */
inorder(ptr.left);

/* then print the data of node */
System.out.print(ptr.key + " ");

/* now recur on right child */
inorder(ptr.right);
}

void preorder(Node ptr)
{
if (ptr == null)
return;

/* first print data of node */
System.out.print(ptr.key + " ");

/* then recur on left sutree */
preorder(ptr.left);

/* now recur on right subtree */
preorder(ptr.right);
}

public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);

System.out.println("Preorder traversal");
tree.preorder(tree.root);

System.out.println("\nInorder traversal");
tree.inorder(tree.root);

System.out.println("\nPostorder traversal");
tree.postorder(tree.root);
}
}

Output :

Preorder traversal
1 2 4 5 3
Inorder traversal 
1 2 4 5 3 
Postorder traversal
4 5 2 3 1