Uploaded December 2018 | Updated November 2026, 3 hours ago
Try Our Full Platform: nas.io/backtobackswe
πΉ Intuitive Video Explanations
βNew Unseen Questions
π Get All Solutions
DFS and BFS are not just graph search algorithms. They are a fundamental method for searching relationships in a certain way and visiting nodes of any sort in a desired order.
These relationships may be represented in a graph, or we may be checking the distance one string is in character changes from another string, OR we may be traversing a tree a certain way.
These are searching concepts, not just graph concepts.
Implementation
DFS can be done iteratively using a stack or done recursively because the call stack will serve as the stack to remember points to backtrack to.
A stack structure can replace our stack frames from recursion, this is why DFS can be written recursively, due to the Last-In-First-Out (LIFO) of the order nodes are processed.
BFS is done iteratively. It uses a queue that has a First-In-First-Out processing order.
Use Cases
DFS is good for things like backtracking, getting to leaf nodes in a tree, or anything where we want to prioritize going very deep into a path and exhausting possibilities before coming back.
BFS is better for things like finding if a path exists between one node to another since it prioritizes width of search over depth (hence "breadth-first") and finding distance or "levels" something is away from something else.
The Method
1.) Choose the data structure based on the search.
2.) Add the start node.
3.) Remove the a node from the data structure.
4.) If the node has not been seen
4a.) Mark it as seen in the "seen" set.
4b.) Do work on the node.
5.) For each of the children
5a.) If child has not been seen (not bee processed)
5ai.) Add the child to the data structure.
Repeat while the data structure is not empty.
Time Complexities
If relationships are represented with an adjacency list then:
Time: O(V + E)
Space: O(V)*
Where V is the total number of vertices (or nodes) visited and E is the total numbers of edges traversed.
*Although things will vary. We only care about the MAXIMUM amount of nodes in the data structure at one time. If we are doing DFS on balanced tree the space complexity would be O(h) where h is the height of the tree since we would only have a path h nodes long at MAX living on the stack. Same for if we do a level order traversal of a tree. The space will only be the MAXIMUM WIDTH of the tree because we would only keep that many nodes on the queue at MAX at one time. And on and on...just depends, ask your interviewer whether they want worst, average, or best case analysis.
"adjacency list" means each node stores its adjacent neighbors in a list
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Try Our Full Platform: nas.io/backtobackswe
πΉ Intuitive Video Explanations
βNew Unseen Questions
π Get All Solutions
DFS and BFS are not just graph search algorithms. They are a fundamental method for searching relationships in a certain way and visiting nodes of any sort in a desired order.
These relationships may be represented in a graph, or we may be checking the distance one string is in character changes from another string, OR we may be traversing a tree a certain way.
These are searching concepts, not just graph concepts.
Implementation
DFS can be done iteratively using a stack or done recursively because the call stack will serve as the stack to remember points to backtrack to.
A stack structure can replace our stack frames from recursion, this is why DFS can be written recursively, due to the Last-In-First-Out (LIFO) of the order nodes are processed.
BFS is done iteratively. It uses a queue that has a First-In-First-Out processing order.
Use Cases
DFS is good for things like backtracking, getting to leaf nodes in a tree, or anything where we want to prioritize going very deep into a path and exhausting possibilities before coming back.
BFS is better for things like finding if a path exists between one node to another since it prioritizes width of search over depth (hence "breadth-first") and finding distance or "levels" something is away from something else.
The Method
1.) Choose the data structure based on the search.
2.) Add the start node.
3.) Remove the a node from the data structure.
4.) If the node has not been seen
4a.) Mark it as seen in the "seen" set.
4b.) Do work on the node.
5.) For each of the children
5a.) If child has not been seen (not bee processed)
5ai.) Add the child to the data structure.
Repeat while the data structure is not empty.
Time Complexities
If relationships are represented with an adjacency list then:
Time: O(V + E)
Space: O(V)*
Where V is the total number of vertices (or nodes) visited and E is the total numbers of edges traversed.
*Although things will vary. We only care about the MAXIMUM amount of nodes in the data structure at one time. If we are doing DFS on balanced tree the space complexity would be O(h) where h is the height of the tree since we would only have a path h nodes long at MAX living on the stack. Same for if we do a level order traversal of a tree. The space will only be the MAXIMUM WIDTH of the tree because we would only keep that many nodes on the queue at MAX at one time. And on and on...just depends, ask your interviewer whether they want worst, average, or best case analysis.
"adjacency list" means each node stores its adjacent neighbors in a list
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw








![Compute All Mnemonics For A Phone Number (Recursion/Backtracking Problem)
Try Our Full Platform: https://nas.io/backtobackswe
πΉ Intuitive Video Explanations
βNew Unseen Questions
π Get All Solutions
Question: Each digit, apart from 0 and 1, in a phone keypad corresponds to one of three or four letters of the alphabet. Write a program which takes asinput a phone number (specified as a string of digits) and returns all possible character sequences that correspond to the phone number.
3 Keys To Backtracking:
Our choice: At each number we can choose certain letters
Our constraints: none really
Our goal: Get a string as ling as the original number given
Time:
O(4^n) * O(1) * O(n) = O(n(4^n)) [weak upper bound]
Since there are no more than 4 possible characters for each digit, there will be O(4^n) function calls at max.
Each call of the function will make at max 4 more calls. 4 * 4 * 4 * 4 * 4... = 4^n, n being the amount of digits provided as input.
O(1) work in each function call for the most part
O(n) time to copy the string over to the answer list in each base case since that is done character by character.
Space:
O(n) + O(4^n) = O(4^n)
Our recursion tree will go at max n calls deep.
We will have at max 4 choices at each digits so total we have roughly 3^n or 4^n total mneumonics that pan out and get stored in the result array.
One could get more mathematically rigorous but that approximation is enough for an interview situation.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: https://www.youtube.com/user/tusharroy2525
GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: https://www.youtube.com/user/VSympathyV
Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is 7.7 in Elements of Programming Interviews. Compute All Mnemonics For A Phone Number (Recursion/Backtracking Problem)](https://i.ytimg.com/vi/a-sMgZ7HGW0/mqdefault.jpg)

