Breadth First Search & Depth First Search Part I (Tree Travesal)

The difference between the two traversal orders lies in the choice of Container.

·         For depth first use a stack. (The recursive implementation uses the call-stack...)

·         For breadth-first use a queue.

A sample program :

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BFS_DFS {

    public void bfs(Node root) {
        Queue q = new LinkedList();
        if (root == null)
            return;
        q.add(root);
        while (!q.isEmpty()) {
            Node n = (Node) q.remove();
            System.out.print(" " + n.data);
            if (n.left != null)
                q.add(n.left);
            if (n.right != null)
                q.add(n.right);
        }
    }

    public void dfs(Node root) {
        Stack stk = new Stack();
        Node temp = root;
        while (!stk.isEmpty() || temp != null) {
            if (temp != null) {
                stk.push(temp);
                temp = temp.left;
            } else {
                Node node = stk.pop();
                System.out.print(" " + node.data);
                temp = node.right;
            }
        }
    }

    public void dfs_recursive(Node node) {
        if (node == null)
            return;
        dfs_recursive(node.left);
        System.out.print(" " + node.data);
        dfs_recursive(node.right);

    }

    public static void main(String[] args) throws java.lang.Exception {
        Node root = new Node(5);
        root.left = new Node(10);
        root.right = new Node(15);
        root.left.left = new Node(20);
        root.left.right = new Node(25);
        root.right.left = new Node(30);
        root.right.right = new Node(35);

        BFS_DFS i = new BFS_DFS();
        System.out.println("Breadth First Search : ");
        i.bfs(root);

        System.out.println("");
        System.out.println("depth First Search stack : ");
        i.dfs(root);

        System.out.println("");
        System.out.println("depth First Search recursive : ");
        i.dfs_recursive(root);
    }
}

class Node {
    int data;
    Node left;
    Node right;

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

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }
}

If you know a solution is not far from the root of the tree, a breadth first search (BFS) might be better. If the tree is very deep and solutions are rare, depth first search (DFS) might take an extremely long time, but BFS could be faster. If the tree is very wide, a BFS might need too much memory, so it might be completely impractical. If solutions are frequent but located deep in the tree, BFS could be impractical.

Here’s an example of what a BFS would look like. This is something like Level Order Tree Traversal where we will use QUEUE with ITERATIVE approach (Mostly RECURSION will end up with DFS)

Comparing BFS and DFS, the big advantage of DFS is that it has much lower memory requirements than BFS, because it’s not necessary to store all of the child pointers at each level. Depending on the data and what you are looking for, either DFS or BFS could be advantageous  

Depth First Search is commonly used when you need to search the entire tree. It's easier to implement (using recursion) than BFS, and requires less state: While BFS requires you store the entire 'frontier', DFS only requires you store the list of parent nodes of the current element.

DFS is more space-efficient than BFS, but may go to unnecessary depths.

Their names are revealing: if there's a big breadth (i.e. big branching factor), but very limited depth (e.g. limited number of "moves"), then DFS can be more preferrable to BFS

Depth-first Search

Depth-first searches are often used in simulations of games (and game-like situations in the real world). In a typical game you can choose one of several possible actions. Each choice leads to further choices, each of which leads to further choices, and so on into an ever-expanding tree-shaped graph of possibilities.

For example in games like Chess, tic-tac-toe when you are deciding what move to make, you can mentally imagine a move, then your opponent’s possible responses, then your responses, and so on. You can decide what to do by seeing which move leads to the best outcome. Only some paths in a game tree lead to your win, some lead to a win by your opponent. When you reach such an ending, you must back up, or backtrack, to a previous node and try a different path. In this way you explore the tree until you find a path with a successful conclusion. Then you make the first move along this path.

Breadth-first search

The breadth-first search has an interesting property: It first finds all the vertices that are one edge away from the starting point, then all the vertices that are two edges away, and so on. This is useful if you’re trying to find the shortest path from the starting vertex to a given vertex. 

Breadth-first search can used for finding the neighbour nodes in peer to peer networks like BitTorrent, GPS systems to find nearby locations, social networking sites to find people in the specified distance and things like that.

Depth-first searches are often used in simulations of games (and game-like situations in the real world). In a typical game you can choose one of several possible actions. Each choice leads to further choices, each of which leads to further choices, and so on into an ever-expanding tree-shaped graph of possibilities.

What are BFS and DFS for Binary Tree?
A Tree is typically traversed in two ways:

 Breadth First Traversal (Or Level Order Traversal)

 Depth First Traversals

  Inorder Traversal (Left-Root-Right)

  Preorder Traversal (Root-Left-Right)

Postorder Traversal (Left-Right-Root) 

1.      Extra Space required for Level Order Traversal is O(w) where w is maximum width of Binary Tree. In level order traversal, queue one by one stores nodes of different level.

2.      Extra Space required for Depth First Traversals is O(h) where h is maximum height of Binary Tree. In Depth First Traversals, stack (or function call stack) stores all ancestors of a node.

3.      Depth First Traversals are typically recursive and recursive code requires function call overheads.

4.      The most important points is, BFS starts visiting nodes from root while DFS starts visiting nodes from leaves. So if our problem is to search something that is more likely to closer to root, we would prefer BFS. And if the target node is close to a leaf, we would prefer DFS.

BFS gives shortest solution

Only difference is “next vertex” choice § BFS uses a queue § DFS uses a stack (recursion)

DFS keeps walking down a path until it is forced to backtrack. It backtracks until it finds a new path to go down. Think: Solving a maze. It results in a search tree, called the depth-first search tree. In general, the DFS tree will be very different than the BFS tree.