Breadth-First Search and Depth-First Search are two techniques of traversing graphs and trees. In this tutorial, we will focus mainly on BFS and DFS traversals in trees.
What is Depth First Search (DFS)?
The algorithm begins at the root node and then it explores each branch before backtracking. It is implemented using stacks. Often while writing the code, we use recursion stacks to backtrack. By using recursion we are able to take advantage of the fact that left and right subtrees are also trees and share the same properties.
For Binary trees, there are three types of DFS traversals.
- In-Order
- Pre-Order
- Post-Order
What is Breadth-First Search (BFS)?
This algorithm also begins at the root node and then visits all nodes level by level. That means after the root, it traverses all the direct children of the root. After all direct children of the root are traversed, it moves to their children and so on. To implement BFS we use a queue.
For Binary trees, we have Level Order Traversal which follows BFS.
Implementation of BFS and DFS in Java
Let the tree under consideration be:
The structure of TreeNode class is as follows :
static class TreeNode {
int data;
TreeNode left, right;
public TreeNode(int key) {
data = key;
left = right = null;
}
}
1. Pre-Order Traversal
In pre-order traversal of a binary tree, we first traverse the root, then the left subtree and then finally the right subtree. We do this recursively to benefit from the fact that left and right subtrees are also trees.
The algorithm for pre-order traversal is as follows:
- Traverse the root.
- Call preorder() on the left subtree.
- Call preorder() on the right subtree.
The Pre-Order traversal of the tree above is:
0 1 3 4 2
The java code is as follows:
static void preorder(TreeNode TreeNode) {
if (TreeNode == null)
return;
// Traverse root
System.out.print(TreeNode.item + "->");
// Traverse left
preorder(TreeNode.left);
// Traverse right
preorder(TreeNode.right);
}
2. In-Order Traversal
In-order traversal of a binary tree first traverses the left subtree then the root and finally the right subtree.
The algorithm for in-order traversal is as follows:
- Call inorder() on left subtree.
- Traverse the root.
- Call inorder() on right subtree.
The in-order traversal of the tree above is:
3 1 4 0 2
The java code is as follows :
static void inorder(TreeNode TreeNode) {
if (TreeNode == null)
return;
// Traverse left
inorder(TreeNode.left);
// Traverse root
System.out.print(TreeNode.item + "->");
// Traverse right
inorder(TreeNode.right);
}
3. Post-Order Traversal
Post-order traversal of a binary tree first traverses the left subtree then the right subtree and then finally the root.
The algorithm for post-order traversal is as follows:
- Call postorder() on left subtree.
- Call postorder() on right subtree.
- Traverse the root.
The post-order traversal of the tree above is:
3 4 1 2 0
The java code is as follows :
static void postorder(TreeNode TreeNode) {
if (TreeNode == null)
return;
// Traverse left
postorder(TreeNode.left);
// Traverse right
postorder(TreeNode.right);
// Traverse root
System.out.print(TreeNode.item + "->");
}
4. Level-Order Traversal
Level order traversal uses a queue to keep track of nodes to visit. After visiting a node, its children are put in the queue. To get a new node to traverse, we take out elements from the queue.
The algorithm is as follows:
- Initialize an empty queue
- Start with setting temp as root
- Run a Loop till queue is not empty
- Print data from temp.
- Enqueue temp’s children in the order left then right.
- Dequeue a node from the queue and assign it’s value to temp.
Level order traversal of the tree above is :
0 1 2 3 4
The java code is as follows :
static void printLevelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode temp = queue.poll();
System.out.print(temp.data + " ");
/*add left child to the queue */
if (temp.left != null) {
queue.add(temp.left);
}
/*add right right child to the queue */
if (temp.right != null) {
queue.add(temp.right);
}
}
}
Complete Code Implementation of BFS and DFS in Java
The complete Java code is given below :
package com.JournalDev;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static class TreeNode {
int data;
TreeNode left, right;
public TreeNode(int key) {
data = key;
left = right = null;
}
}
static void preorder(TreeNode TreeNode) {
if (TreeNode == null)
return;
// Traverse root
System.out.print(TreeNode.data + " ");
// Traverse left
preorder(TreeNode.left);
// Traverse right
preorder(TreeNode.right);
}
static void inorder(TreeNode TreeNode) {
if (TreeNode == null)
return;
// Traverse left
inorder(TreeNode.left);
// Traverse root
System.out.print(TreeNode.data + " ");
// Traverse right
inorder(TreeNode.right);
}
static void postorder(TreeNode TreeNode) {
if (TreeNode == null)
return;
// Traverse left
postorder(TreeNode.left);
// Traverse right
postorder(TreeNode.right);
// Traverse root
System.out.print(TreeNode.data + " ");
}
static void printLevelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode tempNode = queue.poll();
System.out.print(tempNode.data + " ");
/*add left child to the queue */
if (tempNode.left != null) {
queue.add(tempNode.left);
}
/*add right right child to the queue */
if (tempNode.right != null) {
queue.add(tempNode.right);
}
}
}
public static void main(String args[])
{
TreeNode root = new TreeNode(0);
root.left = new TreeNode(1);
root.right = new TreeNode(2);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(4);
System.out.println("Inorder traversal");
inorder(root);
System.out.println("\nPreorder traversal ");
preorder(root);
System.out.println("\nPostorder traversal");
postorder(root);
System.out.println("\nLevelorder traversal");
printLevelOrder(root);
}
}
Output :
Inorder traversal
3 1 4 0 2
Preorder traversal
0 1 3 4 2
Postorder traversal
3 4 1 2 0
Levelorder traversal
0 1 2 3 4
Conclusion
This tutorial was about BFS and DFS traversals in binary trees. To get DFS implementation in C++ refer to this tutorial. For C++ implementation of level order traversal refer to this tutorial.
