Binary tree traversal in Java - Preorder,Inorder,Postorder.

Tree traversal:- In order to process binary tree, the mechanism(different ways) of visiting nodes of tree is termed as tree traversal. Since tree is a non-linear data structure so there are different possible ways to traverse node of trees, as contrast to sequential data structure(stacks, linked list and queues) - nodes are visited in sequential order.

Traversal classification:- Tree traversal may be classified in following category:-

• Based on current nodes data processing - D represents data of current node, L left child and R right child
  1. Preorder (DLR) - First data of current node is processed followed by left and right child
  2. Inorder (LDR) - First left node is processed followed by current node and then right child
  3. Postorder (LRD) - First left and right child is processed and after that current node is processed.
• Based on hierarchy of tree nodes -
  1. Level order traversal
  2. Zig-zag traversal and many more...  

In following post, we will see recursive version of preorder, inorder and postorder traversal.Consider following binary tree for further discussion :-

Definition of Preorder traversal:- In preorder traversal, each node is processed before either of its sub-tree(left and right). Once current node is processed, left sub-tree is processed and control return back to current node and then right sub-tree is processed, so in recursive call stack maintains references of left and right children. It can be summarize as :-
1. Visit the root and process data
2. Traverse to left subtree
3. Traverse to right subtree.
In preorder traversal of above tree, nodes would be visited in following order:- 12 , 23 , 11, 43, 18, 12

/* preOrder traversal - Recursive version */
public void preorderTraversal(Node root, StringBuffer sbr) {
 if (root == null)
  return;
 /* Append node data in string buffer */
 sbr.append(root.getData() + " ");
 preorderTraversal(root.getLeftChild(), sbr);
 preorderTraversal(root.getRightChild(), sbr);
}

Definition of Inorder traversal:- In inorder traversal, left sub-tree is pocessed first and control return back to current node and finally right subtree is processed. In recursive call stack (LIFO) maintains references of left and right children and helps in processing nodes in particular order.It can be summarized as:
1. Traverse to left subtree
2. Visit the root and process data
3. Traverse to right subtree.
In preOrder traversal of above tree, nodes would be visited in following order:- 11 23 43 12 12 18

/* inOrder traversal - Recursive version */
public void inorderTraversal(Node root, StringBuffer sbr) {
 if (root == null)
  return;
 inorderTraversal(root.getLeftChild(), sbr);
 /* Append node data in string buffer */
 sbr.append(root.getData() + " ");
 inorderTraversal(root.getRightChild(), sbr);
}

Definition of Postorder traversal:- In postorder traversal, first left subtree is processed followed by right subtree and then control returns back to current node. In recursive call stack (LIFO) maintains references of left and right children and helps in processing nodes in particular order.It can be summarize as :-
1. Traverse to left subtree
2. Traverse to right subtree.
3.Visit the root and process data
In postOrder traversal for above tree, nodes would be visited in following order:- 11 43 23 12 18 12

/* postOrder traversal - Recursive version */
public void postorderTraversal(Node root, StringBuffer sbr) {
 if (root == null)
  return;
 postorderTraversal(root.getLeftChild(), sbr);
 postorderTraversal(root.getRightChild(), sbr);
 /* Append node data in string buffer */
 sbr.append(root.getData() + " ");
}

Complete sample program - Preorder,Inorder,Postorder

package com.devinline.trees;

public class BinaryTree {
 Node root;

 public BinaryTree() {
  root = null;
 }

 public Node createTree() {
  if (root == null) {
   root = new Node(12);
  }
  root.setLeftChild(new Node(23));
  root.setRightChild(new Node(18));
  root.getLeftChild().setLeftChild(new Node(11));
  root.getLeftChild().setRightChild(new Node(43));
  root.getRightChild().setLeftChild(new Node(12));

  return root;
 }

 /* preOrder traversal - Recursive version */
 public void preorderTraversal(Node root, StringBuffer sbr) {
  if (root == null)
   return;
  /* Append node data in string buffer */
  sbr.append(root.getData() + " ");
  preorderTraversal(root.getLeftChild(), sbr);
  preorderTraversal(root.getRightChild(), sbr);
 }

 /* inOrder traversal - Recursive version */
 public void inorderTraversal(Node root, StringBuffer sbr) {
  if (root == null)
   return;
  inorderTraversal(root.getLeftChild(), sbr);
  /* Append node data in string buffer */
  sbr.append(root.getData() + " ");
  inorderTraversal(root.getRightChild(), sbr);
 }

 /* postOrder traversal - Recursive version */
 public void postorderTraversal(Node root, StringBuffer sbr) {
  if (root == null)
   return;
  postorderTraversal(root.getLeftChild(), sbr);
  postorderTraversal(root.getRightChild(), sbr);
  /* Append node data in string buffer */
  sbr.append(root.getData() + " ");
 }

 /* Level order traversal - Recursive version */
 public void levelorderTraversal(Node root, StringBuffer sbr) {
  if (root == null)
   return;
  postorderTraversal(root.getLeftChild(), sbr);
  postorderTraversal(root.getRightChild(), sbr);
  /* Append node data in string buffer */
  sbr.append(root.getData() + " ");
 }

 public static void main(String[] args) {
  BinaryTree bt = new BinaryTree();
  Node root = bt.createTree();
  StringBuffer sbr = new StringBuffer();
  bt.preorderTraversal(root, sbr);
  System.out.println("Pre order traversal:\t" + sbr.toString());
  sbr = new StringBuffer();
  bt.inorderTraversal(root, sbr);
  System.out.println("In order traversal: \t" + sbr.toString());
  sbr = new StringBuffer();
  bt.postorderTraversal(root, sbr);
  System.out.println("Post order traversal:\t" + sbr.toString());
 }
}

class Node {

 private int data;
 private Node leftChild;
 private Node rightChild;

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

 public int getData() {
  return data;
 }

 public void setData(int data) {
  this.data = data;
 }

 public Node getLeftChild() {
  return leftChild;
 }

 public void setLeftChild(Node leftChild) {
  this.leftChild = leftChild;
 }

 public Node getRightChild() {
  return rightChild;
 }

 public void setRightChild(Node rightChild) {
  this.rightChild = rightChild;
 }

}

========Sample output==========
Pre order traversal:  12 23 11 43 18 12
In order traversal:  11 23 43 12 12 18
Post order traversal: 11 43 23 12 18 12

============================