Traversing binary tree and graphs in Java

A tree node class definition.

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

In order traversal. Print all nodes in order from a binary tree. left, current, and then right.

public void inOrder(Node node) {
	if (node != null) {
		inOrder(node.left);
		System.out.println(node.data);
		inOrder(node.right);	
	}
}

Pre order traversal. Print current node first before its child nodes. current, left, and then right.

public void preOrder(Node node) {
	if (node != null) {
		System.out.println(node.data);
		preOrder(node.left);
		preOrder(node.right);
	}
}

Post order traversal. Print child nodes first and then current node, left, right, and then current.

public void postOrder(Node node) {
	if (node != null) {
		postOrder(node.left);
		postOrder(node.right);
		System.out.println(node.data);
	}
}

Class definitions for a graph. The Graph class is needed because a graph can have more than one root nodes and each of them can be isolated from others. Thus, sometimes you can’t visit all the nodes from a single root node.

public class Graph {
	public Node[] nodes;
}

public class Node {
	int data;
	boolean isVisited;
	Node [] nodes;
	public Node(int data) {
		this.data = data;
	}
}

Search a graph using DFS, Depth First Search.

public void dfsSearch(Node root) {
	if (root == null) return;

	System.out.println(root.data);
	root.visited = true;

	for (Node node : root.nodes) {
		if (!node.isVisited) {
			dfsSearch(node);
		}
	}
}

Search a graph using BFS, Breadth First Search.

public void bfsSearch(Node root) {
	Queue<Node> nodeQueue = new Queue<>();
	root.isVisited = true;
	nodeQueue.enqueue(root);

	while (!nodeQueue.isEmpty()) {
		Node node = nodeQueue.dequeue();
		System.out.println(node.data);

		for (Node n : node.nodes) {
			if (!n.isVisited) {
				n.isVisited = true;
				nodeQueue.enqueue(n);
			}
		}
	}
}