What’s the difference between DFS and BFS?

 

DFS (Depth First Search) and BFS (Breadth First Search) are search algorithms used for graphs and trees. When you have an ordered tree or graph, like a BST, it’s quite easy to search the data structure to find the node that you want. But, when given an unordered tree or graph, the BFS and DFS search algorithms can come in handy to find what you’re looking for. The decision to choose one over the other should be based on the type of data that one is dealing with.

In a breadth first search, you start at the root node, and then scan each node in the first level starting from the leftmost node, moving towards the right. Then you continue scanning the second level (starting from the left) and the third level, and so on until you’ve scanned all the nodes, or until you find the actual node that you were searching for. In a BFS, when traversing one level, we need some way of knowing which nodes to traverse once we get to the next level. The way this is done is by storing the pointers to a level’s child nodes while searching that level. The pointers are stored in FIFO (First-In-First-Out) queue. This, in turn, means that BFS uses a large amount of memory because we have to store the pointers.

Subscribe to our newsletter for more free interview questions.

An example of BFS

Here’s an example of what a BFS would look like. The numbers represent the order in which the nodes are accessed in a BFS:

In a depth first search, you start at the root, and follow one of the branches of the tree as far as possible until either the node you are looking for is found or you hit a leaf node ( a node with no children). If you hit a leaf node, then you continue the search at the nearest ancestor with unexplored children.

An example of DFS

Here’s an example of what a DFS would look like. The numbers represent the order in which the nodes are accessed in a DFS:

Differences between DFS and BFS

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.

For example, given a family tree if one were looking for someone on the tree who’s still alive, then it would be safe to assume that person would be on the bottom of the tree. This means that a BFS would take a very long time to reach that last level. A DFS, however, would find the goal faster. But, if one were looking for a family member who died a very long time ago, then that person would be closer to the top of the tree. Then, a BFS would usually be faster than a DFS. So, the advantages of either vary depending on the data and what you’re looking for.

Hiring? Job Hunting? Post a JOB or your RESUME on our JOB BOARD >>

FOLLOW Varoon Sahgal, Author of ProgrammerInterviewon
  • Hrahsa chowdary

    awsome….! Explanatio… Good

  • Navnath Chinchore

    example is too bad not able to understand …!!

  • Hoàng Trần Việt

    i don’t understand

  • Raja

    awesome explanation :)

  • Naresh

    Good tutorial man! …But Seriously…Example killed me!

  • venkatesh

    Very nice articles to clear basic concepts keep uploading more :)

  • Shashi

    BFS and DFS are primarily to traverse in a graph.
    why all the explanation here talks about trees only?

    • Patrick

      tree is also a graph. Remember this is unordered tree so there is no concept of left or right child

  • Colin

    The last paragraph is a bit confusing because the kind of family tree being considered is not defined. I understand that it’s a tree that is rooted at an ancestor, and which gives all descendants of this ancestor. But when I think of a family tree, I see it rooted at myself, and giving my ancestors. In this case, BFS would be faster at finding somebody who’s still alive.

  • Angus Cheng

    The examples of when to use DFS/BFS ‘killed’ me.

    • http://arungupta.co.in/blog ARUN GUPTA

      mee too my friend.

    • Gustavo Maloste

      Did the author changed the examples? It looks good for me

  • irfan khan

    really nice one..

  • sonuuu

    very nice and easy to understand

  • Bharath

    Nice tutorial with good examples. Thanks for putting all the topics together :)

  • http://about.me/yesi.livera copaeci

    Thank you :)

  • mert

    Nice tutorial.Thanks buddy.