Depth-First Search and Breadth-First Search: Navigating Binary Trees in Java
Learn in this Java tutorial how Breadth-First Search and Depth-First Search can be used for effective binary tree traversal. From explaining the algorithms to providing a complete Java implementation, discover everything you need to successfully navigate through binary trees. Dive in and master the art of tree traversal with ease!
What is Depth First Search (DFS)?
DFS starts at the root of a tree and explores each branch before backtracking. This method is typically implemented using stacks. By using recursion, we can 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)?
BFS also starts at the root and then visits all nodes level by level. This means it first traverses all direct children of the root, and once they are traversed, it moves to their children, and so on. BFS is implemented using a queue.
For binary trees, we use Level-Order Traversal, which follows BFS.
Implementing BFS and DFS in Java
The structure of the 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
Pre-Order traversal of a binary tree first visits the root, then the left subtree, and finally the right subtree. This is done recursively to take advantage of the fact that left and right subtrees are also trees.
The algorithm for Pre-Order Traversal is:
- Visit the root.
- Call preorder() on the left subtree.
- Call preorder() on the right subtree.
The Pre-Order traversal of the tree mentioned above is:
0 1 3 4 2
The Java code implementation looks as follows:
static void preorder(TreeNode TreeNode) {
if (TreeNode == null)
return;
// Visit the root
System.out.print(TreeNode.data + " ");
// Traverse left
preorder(TreeNode.left);
// Traverse right
preorder(TreeNode.right);
}
2. In-Order Traversal
In-Order traversal of a binary tree first visits the left subtree, then the root, and finally the right subtree.
The algorithm for In-Order Traversal is:
- Call inorder() on the left subtree.
- Visit the root.
- Call inorder() on the right subtree.
The In-Order traversal of the tree mentioned above is:
3 1 4 0 2
The Java code implementation looks as follows:
static void inorder(TreeNode TreeNode) {
if (TreeNode == null)
return;
// Traverse left
inorder(TreeNode.left);
// Visit the root
System.out.print(TreeNode.data + " ");
// Traverse right
inorder(TreeNode.right);
}
3. Post-Order Traversal
Post-Order traversal of a binary tree first visits the left subtree, then the right subtree, and finally the root.
The algorithm for Post-Order Traversal is:
- Call postorder() on the left subtree.
- Call postorder() on the right subtree.
- Visit the root.
The Post-Order traversal of the tree mentioned above is:
3 4 1 2 0
The Java code implementation looks as follows:
static void postorder(TreeNode TreeNode) {
if (TreeNode == null)
return;
// Traverse left
postorder(TreeNode.left);
// Traverse right
postorder(TreeNode.right);
// Visit the root
System.out.print(TreeNode.data + " ");
}
4. Level-Order Traversal
Level-Order Traversal uses a queue to keep track of nodes to visit. After a node is visited, its children are added to the queue. To get the next node to traverse, elements are dequeued.
The algorithm is as follows:
- Initialize an empty queue.
- Set temp to the root.
- Run a loop while the queue is not empty:
- Print data from temp.
- Add temp’s children to the queue in left-to-right order.
- Dequeue a node and set its value to temp.
The Level-Order traversal of the tree mentioned above is:
0 1 2 3 4
The Java code implementation looks as follows:
static void printLevelOrder(TreeNode root) {
Queue queue = new LinkedList();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode tempNode = queue.poll();
System.out.print(tempNode.data + " ");
/* Add the left child to the queue */
if (tempNode.left != null) {
queue.add(tempNode.left);
}
/* Add the right child to the queue */
if (tempNode.right != null) {
queue.add(tempNode.right);
}
}
}
Complete Code Implementation of BFS and DFS in Java
The full Java code implementation is as follows:
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;
// Visit the 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);
// Visit the 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);
// Visit the root
System.out.print(TreeNode.data + " ");
}
static void printLevelOrder(TreeNode root) {
Queue queue = new LinkedList();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode tempNode = queue.poll();
System.out.print(tempNode.data + " ");
/* Add the left child to the queue */
if (tempNode.left != null) {
queue.add(tempNode.left);
}
/* Add the 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);
}
}
Conclusion
This tutorial covered BFS and DFS traversals in binary trees. For the C++ implementation of DFS, refer to this tutorial. For the C++ implementation of Level-Order Traversal, refer to this tutorial.
