Breadth-First-Search and Depth-First-Search are the two most popular tree/graph traversal algorithms. Both methods are going to traverse/visit the nodes in tree or graph, however they are different from the way it performs traversals. This difference determines which algorithm to use for a specific problem.

Hope this writing helps to learn the traversal techniques to some extent. Do let me know if any errors.

Traversal Techniques:

Breath First Search:

BFS is actually traversing the nodes level by level. That is, traversing the node first, then its children and then its children’s children. If you consider the following tree,

The root node is A. Its left and right children are B and C. Further its children are D,E,F and G. So the BFS of the above tree is

          ABCDEFG

Here Level Order traversal of a tree is going to be same as BFS since it traverse starting from level 0 till its last level. But not every BFS is level order traversal. For example,

Here the BFS traverse its left and right children first and then its children.

So the BFS traversal of the above tree is 12345. Whereas Level Order traverse level by level. So the level order traversal of the same tree is 13245.

Traversing the graph in BFS way is again going to be same. That visiting the nodes wider as the graph goes.
Consider the following graph,

Let’s traverse starting from Node 0, we first visit 0 and traversing its neighbouring nodes 1 and 2.

Further traversing the next wider level 2 and 5. And Finally 4.

Depth First Search:

As BFS traverse wide, DFS goes deep. It starts from first node, and goes deep in a path till it traverse the leaf node/the last node before start traversing its next path.

In the above tree, it first starts from root node 1, does deep to 2 and more deeper to 4. Node 4 has no children, so it is done with that path visits 5 and traverse back to 1 and starts visiting deep 3,6 and 7.

Further we can traverse in three different ways,

1. Pre-Order: Visiting root first, left node next and finally right node.
2. Inorder: Visiting left first, root node next and finally right node.
3. Post-Order: Visiting left first, right node next and finally root node.

So the traversal of above tree is going to be,

Pre-Order: 1245367
Inorder: 4251637
Post-Order: 4526731

DFS of graph is also goes deep till it traverse all the nodes in the graph.

Implementation:
BFS: FIFO (First In First Out)
In Breadth-First-Search, queue is going to be our hero. Here are the steps to implement BFS programmatically.

1. Put the visited node in queue.
2. Explore its children, add them to queue, and remove the visited node.
3. Visit all the nodes until queue becomes empty.

In the above tree,

1. we first put the root node A in queue. A’s children are B and C. Add them to queue and remove A.
2. Further pull B, add its children D and E to queue and remove B.
3. Pull C, add its children F and G to queue and remove C.
4. D,E,F and G have no children, so pop them from queue.

public void BFS(TreeNode root)
    {
        Queue<Integer> queue = new LinkedList<>();
         queue.add(root);
        while (!queue.isEmpty())
        {
            int size = queue.size();
             for (int i=0;i<size;i++)
			 {
				TreeNode currentNode = queue.poll();
                if(currentNode.left!=null)  queue.add(currentNode.left);
				if(currentNode.right!=null)  queue.add(currentNode.right);
				System.out.print(currentNode.val);
              }
         }
   }
    

DFS: LIFO (Last In First Out)
We are going to get the help of stack, in order to traverse the tree/graph DFS way.

1. Add the visited Node to stack.
2. Pop the Node from stack, explore its children and add them to stack.
3. Explore all the nodes till stack becomes empty.
   Here we are going to see pre-order traversal of the below tree using stack. Same technique can be used to perform both inorder and post-order traversals just by changing the order of visiting nodes.

In above example,

1. First we are visiting Node 1, add them to stack, explore its children and add its right child 3 first and then left child 2.
2. Now the stack has nodes 2 and 3. Explore 2’s children and add its right child 5 and then its left child 4 to stack. And pop 2.
3. Further pop nodes from stack and add its children until stack becomes empty.

public void DFSInOrder(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    stack.push(root);
    while(!stack.isEmpty()) {
        while(current.left != null) {
            current = current.left;                
            stack.push(current);                
        }
        current = stack.pop();
        System.out.print(current.value);
        if(current.right != null) {
            current = current.right;                
            stack.push(current);
        }
    }
}

When to use:
Few problems can be solved using both BFS and DFS.
BFS can be helpful when,
• We want to find the shortest path from any source to destination.
• You want to find there exist a path between two nodes.
• Bipartite Graph
• If you feel the solution exists in fewer levels instead of going deep..

DFS can be helpful when,
• We want to exhaust all possibilities, and check which is best.
• We need to count all possible paths from source to destination.
• Backtracking.

Here is the links for list of problems that can be solved using BFS and DFS.

BFS link
DFS link

Hope this article helped you in some way. Happy Coding!