Traversing a Binary tree

There are several ways to traverse a binary tree in Java, including in-order, pre-order, and post-order traversals.

• In-order traversal visits the left subtree, the current node, and the right subtree in that order. This method can be used to retrieve the elements of the tree in ascending order (for a binary search tree). It can be implemented recursively:

void inOrder(Node root) {
    if (root != null) {
        inOrder(root.left);
        System.out.print(root.data + " ");
        inOrder(root.right);
    }
}

• Pre-order traversal visits the current node, the left subtree, and the right subtree in that order. This method can be used to create a copy of the tree or to get the prefix expression of an expression tree. It can be implemented recursively:

void preOrder(Node root) {
    if (root != null) {
        System.out.print(root.data + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
}

• Post-order traversal visits the left subtree, the right subtree, and the current node in that order. This method can be used to delete the tree or to get the postfix expression of an expression tree. It can be implemented recursively:

void postOrder(Node root) {
    if (root != null) {
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.data + " ");
    }
}

• Breadth-first traversal(also known as Level-Order traversal) visits all the nodes of the current level from left to right before moving to the next level. This method can be implemented using a queue.

void levelOrder(Node root) {
    if (root == null) return;
    Queue<Node> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
        Node n = q.remove();
        System.out.print(n.data + " ");
        if (n.left != null) q.add(n.left);
        if (n.right != null) q.add(n.right);
    }
}

import java.util.*;

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

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

class BinaryTree {
	Node root;

	void inOrder(Node root) {
		if (root != null) {
			inOrder(root.left);
			System.out.print(root.data + " ");
			inOrder(root.right);
		}
	}

	void preOrder(Node root) {
		if (root != null) {
			System.out.print(root.data + " ");
			preOrder(root.left);
			preOrder(root.right);
		}
	}

	void postOrder(Node root) {
		if (root != null) {
			postOrder(root.left);
			postOrder(root.right);
			System.out.print(root.data + " ");
		}
	}

	void levelOrder(Node root) {
		if (root == null)
			return;
		Queue<Node> q = new LinkedList<>();
		q.add(root);
		while (!q.isEmpty()) {
			Node n = q.remove();
			System.out.print(n.data + " ");
			if (n.left != null)
				q.add(n.left);
			if (n.right != null)
				q.add(n.right);
		}
	}

}

public class Main {
	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("inOrder: ");
		tree.inOrder(tree.root);
		System.out.println("\npreOrder: ");
		tree.preOrder(tree.root);
		System.out.println("\npostOrder: ");
		tree.postOrder(tree.root);
		System.out.println("\nlevelOrder: ");
		tree.levelOrder(tree.root);
	}
}

inOrder: 
4 2 5 1 3 
preOrder: 
1 2 4 5 3 
postOrder: 
4 5 2 3 1 
levelOrder: 
1 2 3 4 5 

Related Article : DFS and BFS : Comprehensive Guide