Tree Traversals - Depth First (Recursive Approach)

Tree is a hierarchical data structure and  therefore can be traversed in more than one way unlike liner data structures. Each order of traversal has its own benefits.

Generally there are two main ways to traverse a binary tree -
1. Depth First Traversal
2. Breadth First Traversal

In this particular article we will discuss three ways to traverse a binary tree using Depth First approach. Also we can implement the traversal using either recursive approach or Iterative approach, but here we will go with recursive approach.

For Breadth First or level order Traversal visit this link - Binary Tree - Breadth First or Level Order Traversal

In Depth First traversal there are 3 ways to traverse a binary tree -

1. Inorder Traversal (Left, Root, Right)
   
2. Preorder Traversal (Root, Left, Right)
3. Postorder Traversal (Left, Right, Root)

1. Inorder Traversal - For Inorder Traversal following sequence is followed -

- Visit the left subtree.
- Visit root Node
- Visit right subtree

Basically for each node in the tree first we visit its left node then the node itself and then the right node of the node starting from the root node. But remember that same is true for its left and right node also ie.  if its left and right nodes have children left and right nodes then first we will visit the left node then the node itself and then the right node for both the left and right nodes.

Lets try to understand it with an example.
Suppose we have a binary tree as shown in the figure below - 

Inorder traversal of the this tree woud be - 2 3 4 5 6 8 10 

2. Preorder Traversal - For Preorder Traversal following sequence is followed -

- Visit root Node

- Visit the left subtree

- Visit right subtree

In preorder traversal for each node first we visit the root node then its left node and then right node. This sequence is followed by all nodes recursively.

Preorder traversal of the tree in above diagram would be - 5 3 2 4 8 6 10

3. Postorder Traversal - For Postorder Traversal following sequence is followed -

- Visit the left subtree

- Visit right subtree

- Visit root Node

 In postorder traversal for each node first we visit its left node then its right node and the the node itself. And same rule applies for the left and right children nodes also and so on. 

Postorder traversal of the tree in above diagram would be - 2 4 3 6 10 8 5

Now lets write some code to iterate the tree in all three orders and print the key values in corresponding order. We will be creating a custom binary search tree and implement three methods one for each order using recursive approach. 

package ds.tree;

public class BStree {

	private Node root;

	public BStree(int rootData) {
		this.root = new Node(rootData);
	}

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

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

	public void insert(int data) {
		Node nNode = new Node(data);
		
		Node root = this.root;
		Node nodeB = null;
		while (root != null) {
			nodeB = root;
			if (root.data > data) {
				root = root.left;
			} else {
				root = root.right;
			}
		}
		if(data < nodeB.data)
			nodeB.left = nNode;
		else
			nodeB.right = nNode; 
	}
	
	public void printInOrder() {
		inOrderRec(this.root);
	}
	
	private void inOrderRec(Node root){
		if(root == null)
			return;
		inOrderRec(root.left);
		System.out.print(root.data + " ");
		inOrderRec(root.right);
	}
	
	public void printPreOrder() {
		preOrderRec(this.root);
	}
	
	private void preOrderRec(Node root) {
		if(root == null)
			return;
		System.out.print(root.data + " ");
		preOrderRec(root.left);
		preOrderRec(root.right);
	}
	
	public void printPostOrder() {
		postOrderRec(this.root);
	}
	
	private void postOrderRec(Node root) {
		if(root == null)
			return;
		postOrderRec(root.left);
		postOrderRec(root.right);
		System.out.print(root.data + " ");
	}
}

Now to test our implementation lets write a main class which will use the same data as shown in the diagram above to create a binary search tree and print its keys using all three traversal approcahes.

package ds.tree;

public class BtreeMain {
	
	public static void main(String[] args) {
		BStree bst = new BStree(5);
		bst.insert(3);
		bst.insert(8);
		bst.insert(6);
		bst.insert(4);
		bst.insert(2);
		bst.insert(10);
		
		System.out.println("Inorder Traversal - ");
		bst.printInOrder();
		
		System.out.println("\nPreorder Traversal - ");
		bst.printPreOrder();
		
		System.out.println("\nPostorder Traversal - ");
		bst.printPostOrder();
	}
}

Output: Inorder Traversal - 
2 3 4 5 6 8 10 
Preorder Traversal - 
5 3 2 4 8 6 10 
Postorder Traversal - 
2 4 3 6 10 8 5 

We can do the depth first traversal without recursion also. If you are interested in iterative approach for depth first traversal, visit this link - Tree Traversal - Depth First (Iterative/ Non Recursive Approach)