One of the Most Common Questions in the Coding Interview — Depth-First Search and Breadth-First Search with Python Code and Detailed Illustration

The answer key is FIFO and LIFO… others are much the same actually…

Photo by Nangialai Stoman on Unsplash

Summer has come and passed… The innocent can never last… — Wake Me Up When September Ends by Green Day

Hey there, starting with these lyrics 🎶: “It’s September, wake up!” So, guess what? It’s that time of the year when tons of job opportunities are out there for fresh grads to grab. I’m guessing you’re in the same boat, busy with those job applications (I am too, LOL).

But why am I writing this post, you ask? Well, it’s pretty simple: the technical interview is always a good chance to showcase your skills to the interviewer, and you have to be well prepared for that. Writing this post provides me with a chance to revisit some simple but important coding knowledge. 📝😄

If you can’t explain it to a six-year-old, then you don’t understand it yourself… — Albert Einstein

Content

1. First-In-First-Out (FIFO) v.s. Last-In-First-Out (LIFO)
2. Depth-First Search
3. Breadth-First Search

First-In-First-Out (FIFO) v.s. Last-In-First-Out (LIFO)

Left: First-In-First-Out (FIFO); Right: Last-In-First-Out (LIFO).

They have other names: queue and stack; but they have the same meaning. They share the essential ingredients:

• An array
• Some items to read in and process sequentially

Queue (FIFO): the array that pops out the items in an order based on which the item comes first. In contrast, the items coming in late get out first in the array, and that array is called stack (LIFO).

# storing some integers first for demo
array_FIFO = []
array_LIFO = []

for i in range(10):
  array_FIFO.append(i)
  array_LIFO.append(i)

print(array_FIFO)
print(array_LIFO)
# both arrays become [0, 1, 2, 3, ..., 9]

# FIFO until the array_FIFO is empty
# you should be able to see 0, 1, 2, ..., 9
while len(array_FIFO) > 0:
  item = array_FIFO.pop(0)
  print(item)

# LIFO until the array_LIFO is empty
# you should be able to see 9, 8, 7, ..., 0
while len(array_LIFO) > 0:
  item = array_LIFO.pop() # the last one
  print(item)

Depth-First Search

Before we start, please spend some time on the chart and think about what you have observed. Hint: Look at the array in orange color on the right hand side.

It’s the LIFO method in the orange array! The tree nodes that get in the last come out first :D. So, hey Jasper, how are you going to solve this in the interview? Similarly, it contains all the essential ingredients in Stack and one new thing:

• A stack (or an array)
• A pointer
• Some tree nodes (items)

Firstly, I have to define a tree node as a class:

class Node:
  def __init__(self, val, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right

Make a tree like the one illustrated in the diagram (using recursion here):

tree_structure = {
    1: [2, 8],
    2: [3, 5],
    3: [4, None],
    4: [None, None],
    5: [6, 7],
    6: [None, None],
    7: [None, None],
    8: [None, 9],
    9: [None, None]
}

def build_tree(node_val):
  if node_val is None:
    return None

  left_node = build_tree(tree_structure[node_val][0])
  right_node = build_tree(tree_structure[node_val][1])

  return Node(val=node_val,
              left=left_node,
              right=right_node)

root = build_tree(1)

The algorithm is:

visited = []
to_visit = [root]

while len(to_visit) > 0:
  ptr = to_visit.pop() # Key point
  visited.append(ptr.val)

  if not ptr.right is None:
    to_visit.append(ptr.right)
  
  if not ptr.left is None:
    to_visit.append(ptr.left)

print(visited)
# it gives [1, 2, 3, 4, 5, 6, 7, 8, 9]

Breadth-First Search

Again, it contains:

• A queue (an array in FIFO version)
• A pointer (the same as DFS)
• Some tree nodes (the same as DFS)

The algorithm is (you may also want to notice that only one line is changed here and has made a huge difference in the priority of searching):

visited = []
to_visit = [root]

while len(to_visit) > 0:
  ptr = to_visit.pop(0) # Key point
  visited.append(ptr.val)

  if not ptr.left is None:
    to_visit.append(ptr.left)
  
  if not ptr.right is None:
    to_visit.append(ptr.right)

print(visited)
# it gives [1, 2, 8, 3, 5, 9, 4, 6, 7]

Wrap up a bit…

The concepts of First-In-First-Out (FIFO) and Last-In-First-Out (LIFO), often represented by queues and stacks, respectively, are the the most important things that you have to know in the DFS and BFS.

Depth-First Search (DFS) operates like a stack (LIFO), where nodes added last are processed first. In contrast, Breadth-First Search (BFS) uses a queue (FIFO) to process nodes in a different order than DFS.

And these data structures dominate the whole direction and approach of searching a tree.