## 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 BFSHere’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 DFSHere’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 BFSComparing 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 @programmerintvw FOLLOW Varoon Sahgal, Author of ProgrammerInterviewon
Did the author changed the examples? It looks good for me

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

awsome….! Explanatio… Good

example is too bad not able to understand …!!

i don’t understand

awesome explanation

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

Very nice articles to clear basic concepts keep uploading more

BFS and DFS are primarily to traverse in a graph.

why all the explanation here talks about trees only?

mee too my friend.

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.

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

really nice one..

very nice and easy to understand

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

Thank you

Nice tutorial.Thanks buddy.