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

17 Responses to “DFS vs. BFS”

  1. Gustavo Maloste says:

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

  2. Patrick says:

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

  3. Hrahsa chowdary says:

    awsome….! Explanatio… Good

  4. Navnath Chinchore says:

    example is too bad not able to understand …!!

  5. Hoàng Trần Việt says:

    i don’t understand

  6. Raja says:

    awesome explanation :)

  7. Naresh says:

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

  8. venkatesh says:

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

  9. Shashi says:

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

  10. ARUN GUPTA says:

    mee too my friend.

  11. Colin says:

    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.

  12. Angus Cheng says:

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

  13. irfan khan says:

    really nice one..

  14. sonuuu says:

    very nice and easy to understand

  15. Bharath says:

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

  16. mert says:

    Nice tutorial.Thanks buddy.

Leave a Reply

*