Recursive binary tree traversal algorithm in java (preOrder /postOrder/inOrder)

• Given a binary tree, traverse the binary tree using recursive algorithm.
• Binary tree traversal is categorized into two parts.
  • Depth first search traversal (recursive algorithm)
    • Pre Order Traversal
    • Post Order Traversal
    • In Order Traversal
  • Breadth First search (BFS) or Level Order Traversal (non-recursive) algorithm.

Applications of depth first search:

• Delete all nodes in binary tree using PostOrder traversal
• Find InOrder successor in BST using InOrder traversal
• Find InOrder predecessor in BST using InOrder traversal

Examples of PreOrder, PostOrder & InOrder (DFS) algorithm (java).

Example 1 (PreOrder binary tree traversal):

• In preOrder traversal:
  • We are visit current node, then
  • We visit left child node, then
  • We visit right child node.
• We have shown the preOrder traversal in Fig. 2:

1. Visit parent node or current node
2. Visit left child
3. Visit right child

PreOrder binary tree traversal of binary tree shown in Fig 3 is:
60 20 10 30 80 70 65 75 90 85 95

	public static void preOrder(Node root) {
		if (null == root) {
			return;
		}
		System.out.printf("%d ", root.data);
		preOrder(root.left);
		preOrder(root.right);
	}

Example 2 (PostOrder binary tree traversal):

• In postOrder traversal:
  • We visit left child, then
  • We visit right child, then
  • We visits current node.
• We have shown the postOrder traversal in Fig. 4:

1. Visit left child
2. Visit right child
3. Visit parent node or current node

PostOrder binary tree traversal of binary tree shown in Fig 5 is:
10 30 20 65 75 70 85 95 90 80 60

	public static void postOrder(Node root) {
		if (null == root) {
			return;
		}
		postOrder(root.left);
		postOrder(root.right);
		System.out.printf("%d ", root.data);
	}

Example 3 (InOrder binary tree traversal):

• Using InOrder traversal:
  • We first visits the left child, then
  • Current node, then
  • Right child of binary tree.
• We have shown the inOrder traversal in Fig. 6:

1. Visit left child
2. Visit parent node or current node
3. Visit right child

InOrder binary tree traversal of binary tree shown in Fig 7 is:
10 20 30 60 65 70 75 80 85 90 95

	public static void inOrder(Node root) {
		if (null == root)
			return;
		inOrder(root.left);
		System.out.printf("%d ", root.data);
		inOrder(root.right);
	}

Time complexity of algorithm is O(n).

Program: traverse binary tree in PreOrder, PostOrder & InOrder using java

1.) DFSTraversal Class:

DFSTraversal class performs the following operations:

• preOrder traversal
• postOrder traversal
• inOrder traversal

package org.learn.Question;

public class DFSTraversal {
	
	public static void preOrder(Node root) {
		if (null == root) {
			return;
		}
		System.out.printf("%d ", root.data);
		preOrder(root.left);
		preOrder(root.right);
	}
	
	public static void postOrder(Node root) {
		if (null == root) {
			return;
		}
		postOrder(root.left);		
		postOrder(root.right);
		System.out.printf("%d ", root.data);
	}
	
	public static void inOrder(Node root) {
		if (null == root)
			return;
		inOrder(root.left);
		System.out.printf("%d ", root.data);
		inOrder(root.right);
	}
	
	
}

2.) Node Class:

• Node class is represents the nodes of a binary tree.

package org.learn.Question;

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

	public Node(int num) {
		this.data = num;
		this.left = null;
		this.right = null;
	}

	public Node() {
		this.left = null;
		this.right = null;
	}
	
	public static Node createNode(int number) {
		return new Node(number);
	}
}

3.) App Class:

• We are creating the binary tree in main method.
• We are calling the method of DFSTraversal class to perform preOrder, postOrder and inOrder traversal.

package org.learn.Client;

import org.learn.Question.DFSTraversal;
import org.learn.Question.Node;

public class App {
	public static void main(String[] args) {
		// root level 0
		Node A = Node.createNode(60);
		// Level 1
		Node B = Node.createNode(20);
		Node C = Node.createNode(80);
		// Level 2
		Node D = Node.createNode(10);
		Node E = Node.createNode(30);
		Node F = Node.createNode(70);
		Node G = Node.createNode(90);
		// Level 3
		Node H = Node.createNode(65);
		Node I = Node.createNode(75);
		Node J = Node.createNode(85);
		Node K = Node.createNode(95);

		// connect Level 0 and 1
		A.left = B;
		A.right = C;
		// connect level 1 and level 2
		B.left = D;
		B.right = E;
		C.left = F;
		C.right = G;
		// connect level 2 and level 3
		F.left  = H;
		F.right = I;
		G.left  = J;
		G.right = K;
		
		System.out.println("PreOrder binary tree traversal :");
		DFSTraversal.preOrder(A);
		
		System.out.println("\nPostOrder binary tree traversal :");
		DFSTraversal.postOrder(A);
		
		System.out.println("\nInOrder binary tree traversal : ");
		DFSTraversal.inOrder(A);
	}
}

Output: preOrder, PostOrder & InOrder binary tree traversal using java

PreOrder binary tree traversal :
60 20 10 30 80 70 65 75 90 85 95 
PostOrder binary tree traversal :
10 30 20 65 75 70 85 95 90 80 60 
InOrder binary tree traversal : 
10 20 30 60 65 70 75 80 85 90 95 

Download Code – binary tree traversal algorithm (pre,post & inorder)