In post talks about Depth-First Search or DFS for a Graph Data Structure with example
To solve problems on graphs, we need a mechanism for traveling the graph. graph traversal algorithms are usually called Graph Search Algorithms. like trees traversal algorithms( inorder, preorder, and level order traversals), Graph Search algorithms can be thought of As starting at some source vertex in a graph and searching the graph by going through the edges and marking the vertices. We have mainly two search algorithms for traveling the graphs
- Depth-First Search (DFS)
- Breadth-First Search (BFS)
Depth-First Search(DFS) is a method to explore a tree or graph. In a DFS We go as deep as possible down one path before backing up and trying a different one. DFS algorithm works in a manner similar to the preorder traversal of the trees. like preorder traversal internally this algorithm also using stack.
In this post, we will learn How to write a Java program to do a Binary tree traversal using Depth-First Search (DFS).
In the previous post, Binary Tree Traversal Using Breadth-First Search, we already saw Java implementation for binary tree traversal using Breadth-First Search.
Now we will see How to implement for the binary tree traversal using Depth-First search.
Contrary to the Breadth-First Search (BFS) where nodes within the same level are visited first in Depth-First search traversal is done by moving to the next level of nodes. Control moves to the deepest node and then come back to the parent node when the dead-end is reached.
There are several orderings for Depth-First search of a binary tree- in-order, pre-order, and post-order which are easy to implement using recursion. Apart from that, you can also write a Depth-First search program using a stack in a non-recursive way. So, in this post, we’ll see Recursive Java implementation of in-order, pre-order and post-order traversal of a binary tree as well as iterative (non-recursive) Java implementation.
Binary tree In-order traversal Java program
The logic for In-order traversal of the binary search tree is as follows-
- Recursively traverse the left subtree.
- Visit the root node
- Recursively traverse the right subtree
Note that in-order traversal of the binary search tree visits the nodes in ascending order so in-order traversal is also used for tree sort.
1 2 3 4 5 6 7 8 |
//For traversing in-order public void inOrderTraversal(Node node){ if(node != null){ inOrderTraversal(node.left); node.displayData(); inOrderTraversal(node.right); } } |
Binary tree Pre-order traversal Java program
The logic for pre-order traversal of the binary search tree is as follows-
- Visit the root node
- Recursively traverse the left subtree.
- Recursively traverse the right subtree
1 2 3 4 5 6 7 |
// Pre-order traversal public void preOrderTraversal(Node node){ if(node != null){ node.displayData(); preOrderTraversal(node.left); preOrderTraversal(node.right); } |
Binary tree post-order traversal Java program
The logic for post-order traversal of the binary search tree is as follows-
- Recursively traverse the left subtree.
- Recursively traverse the right subtree
- Visit the root node
1 2 3 4 5 6 7 8 |
//post-order traversal public void postOrderTraversal(Node node){ if(node != null){ postOrderTraversal(node.left); postOrderTraversal(node.right); node.displayData(); } } |
Depth-first search recursive Java program
Below is the complete Java source for traversing a binary tree using Depth-First Search. This program shows the recursive methods for in-order traversal, pre-order traversal, and post-order traversal.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 |
package com.kkjavatutorials.client; public class DepthFirstSearch { //Root Node root node private Node root; public DepthFirstSearch(){ root = null; } /** * This internal class representing binary tree nodes * @author KK JavaTutorials */ private static class Node{ //Data hold by tree mode private int value; private Node left; private Node right; public Node(int value){ this.value = value; left = null; right = null; } public void displayData(){ System.out.print(value + " "); } } public void insert(int i){ root = insert(root, i); } /** * Function to insert node in tree * @param data to insert in binary tree */ public Node insert(Node node, int value){ //If root node is null if(node == null){ return new Node(value); } /* Insert Node to the left if passed value is less than the current node*/ if(value < node.value){ node.left = insert(node.left, value); } /*Insert Node to the right if passed value is greater than the current node*/ else if(value > node.value){ node.right = insert(node.right, value); } return node; } /** * Function for in-order traversal * @param node tree */ public void inOrderTraversal(Node node){ if(node != null){ inOrderTraversal(node.left); node.displayData(); inOrderTraversal(node.right); } } /** * Function for pre-order traversal * @param node tree */ public void preOrderTraversal(Node node){ if(node != null){ node.displayData(); preOrderTraversal(node.left); preOrderTraversal(node.right); } } /** * Function for post-order traversal * @param node tree */ public void postOrderTraversal(Node node){ if(node != null){ postOrderTraversal(node.left); postOrderTraversal(node.right); node.displayData(); } } public static void main(String[] args) { //Create Instance of DepthFirstSearch DepthFirstSearch depthFirstSearch = new DepthFirstSearch(); //Insert Nodes depthFirstSearch.insert(60); depthFirstSearch.insert(70); depthFirstSearch.insert(30); depthFirstSearch.insert(25); depthFirstSearch.insert(38); depthFirstSearch.insert(10); depthFirstSearch.insert(28); depthFirstSearch.insert(32); depthFirstSearch.insert(61); depthFirstSearch.insert(85); //Binary tree in-order traversal System.out.println("Binary tree in-order traversal: "); depthFirstSearch.inOrderTraversal(depthFirstSearch.root); System.out.println(""); //Binary tree post-order traversal System.out.println("Binary tree post-order traversal: "); depthFirstSearch.postOrderTraversal(depthFirstSearch.root); System.out.println(""); //Binary tree pre-order traversal System.out.println("Binary tree pre-order traversal:"); depthFirstSearch.preOrderTraversal(depthFirstSearch.root); } } |
The output of this program:
Binary tree in-order traversal:
10 25 28 30 32 38 60 61 70 85
Binary tree post-order traversal:
10 28 25 32 38 30 61 85 70 60
Binary tree pre-order traversal:
60 30 25 10 28 38 32 70 61 85
Depth-first search Non-Recursive Java program
To write a Java program for Depth-First Search of a binary tree using a non-recursive method a stack is used as a stack data structure is used. Iterative approach implementation for in-order and pre-order traversal is easy to understand.
Iterative implementation for post-order traversal of a binary tree is a bit complex, as you can see in the recursive method the statement to display is after the recursive calls in post-order traversal which makes iterative implementation a bit complex.
Here post-order traversal iterative implementation is done using two stacks. In the first stack, you add root, left, right, and then add root first in the second stack and then the additional order would be right and left in the second stack when popping from the first stack. After that pop from the second stack would give you the post order of left, right, and root.
Here is a complete Java source code for traversing a binary tree using Depth-First Search. In the program, there are iterative methods for in-order traversal, pre-order traversal, and post-order traversal where the stack is used as an auxiliary data structure.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 |
package com.kkjavatutorials.client; import java.util.Stack; public class DepthFirstSearch { //Root Node root node private Node root; public DepthFirstSearch(){ root = null; } /** * This internal class representing binary tree nodes * @author KK JavaTutorials */ private static class Node{ //Data hold by tree mode private int value; private Node left; private Node right; public Node(int value){ this.value = value; left = null; right = null; } public void displayData(){ System.out.print(value + " "); } } public void insert(int i){ root = insert(root, i); } /** * Function to insert node in tree * @param data to insert in binary tree */ public Node insert(Node node, int value){ //If root node is null if(node == null){ return new Node(value); } /* Insert Node to the left if passed value is less than the current node*/ if(value < node.value){ node.left = insert(node.left, value); } /*Insert Node to the right if passed value is greater than the current node*/ else if(value > node.value){ node.right = insert(node.right, value); } return node; } /** * Function for in-order traversal * @param node tree */ public void inOrderTraversal(){ //If root is empty if(root == null){ return; } Stack<Node> s = new Stack<>(); Node current = root; while(current != null || !s.isEmpty()){ //Traverse left subtree while(current != null){ s.push(current); current = current.left; } current = s.pop(); current.displayData(); current = current.right; } } /** * Function for pre-order traversal * @param node tree */ public void preOrderTraversal(){ //If root is empty if(root == null){ return; } Stack<Node> s = new Stack<>(); s.push(root); while(!s.isEmpty()){ Node node = s.pop(); node.displayData(); if(node.right != null){ s.push(node.right); } if(node.left != null){ s.push(node.left); } } } /** * Function for post-order traversal * @param node tree */ public void postOrderTraversal(){ Stack<Node> stack1 = new Stack<>(); Stack<Node> stack2 = new Stack<>(); stack1.push(root); while (!stack1.isEmpty()) { /*Insert root tree into second stack so that it is last to be popped*/ Node node = stack1.pop(); stack2.push(node); /* now follow the post-order of pushing the left and right child*/ if(node.left!=null){ stack1.push(node.left); } if(node.right!=null){ stack1.push(node.right); } } //Pop Item from stack2 while(!stack2.isEmpty()){ stack2.pop().displayData(); } } public static void main(String[] args) { //Create Instance of DepthFirstSearch DepthFirstSearch depthFirstSearch = new DepthFirstSearch(); //Insert Nodes depthFirstSearch.insert(60); depthFirstSearch.insert(70); depthFirstSearch.insert(30); depthFirstSearch.insert(25); depthFirstSearch.insert(38); depthFirstSearch.insert(10); depthFirstSearch.insert(28); depthFirstSearch.insert(32); depthFirstSearch.insert(61); depthFirstSearch.insert(85); //Binary tree in-order traversal System.out.println("Binary tree in-order traversal: "); depthFirstSearch.inOrderTraversal(); System.out.println(""); //Binary tree post-order traversal System.out.println("Binary tree post-order traversal: "); depthFirstSearch.postOrderTraversal(); System.out.println(""); //Binary tree pre-order traversal System.out.println("Binary tree pre-order traversal:"); depthFirstSearch.preOrderTraversal(); } } |
The output of this program:
Binary tree in-order traversal:
10 25 28 30 32 38 60 61 70 85
Binary tree post-order traversal:
10 28 25 32 38 30 61 85 70 60
Binary tree pre-order traversal:
60 30 25 10 28 38 32 70 61 85
Advantages of DFS
- Depth First Search on a binary tree generally requires less memory than Breadth-First Search
- Depth-First Search can be easily implemented using recursion
Disadvantages of DFS
- DFS does not necessarily find the shortest path to a node while Breadth-First Search does
Application of DFS
- Topological sorting
- Finding connected components
- Finding articulation points (cut vertices) of the graph
- Finding a strongly connected components
- solving puzzles
Comparing DFS and BFS Algorithms:
The big advantage of DFS is that it has much lower memory requirements than BFS because it’s not required to store all of the children pointers at each level. Depending on the data and what we are looking for, either DFS and BFS can be advantageous. For example in a family tree if we are looking for someone who is still alive and if we assume that person would be at the bottom of the tree then DFS is a better choice. BFS usually takes a very long time to reach that last level.
The DFS algorithm finds the goal faster. Now if we are looking for a family member who died a very long time ago then the person would be closer to the top of the tree. In this case, BFS finds faster than the DFS. S0 the advantages of either vary depending on the data and what we are looking for. DFS is related to the preorder traversal of a tree. Like preorder traversal, DFS digits each node before its children. The BFS algorithm works similarly to the level order traversal of the trees.
If someone asks that the DFS is better or BFS is better. The answer depends on the type of problem that they are trying to solve. BFS visits each level one at a time and if we know the solution we are searching for is at low depth then BFS is good. DFS is a better choice if the solution is maximum depth. The below table shows the difference between DFS and BFS in terms of their applications
Applications | DFS | BFS |
Spanning forest, connected components, paths, cycles | YES | YES |
Shortest Paths | YES | |
Minimal use of memory space | YES |
You May Also Like:
Introduction to Graph Data Structure?
Important Types of Graph Data Structure
Breadth-First Search for a Graph Data Structure
That’s all about Depth-First Search or DFS for a Graph Data Structure
If you have any feedback or suggestion please feel free to drop in below comment box.