Balanced Binary Tree (Practice Interview Question)

You only have 3 free questions left (including this one).

But it doesn't have to end here! Sign up for the 7-day coding interview crash course and you'll get a free Interview Cake problem every week.

You're in!

Write a function to see if a binary tree ↴

Binary trees are a fundamental data structure that organizes items in a hierarchical, branching way. Each node in a binary tree has a value and pointers to two other nodes - a left child and a right child.

class BinaryTreeNode(object): def __init__(self, value): self.value = value self.left = None self.right = None

Binary trees are surprisingly powerful and efficient. With balanced implementations, most operations are logarithmic time complexity, meaning operations on binary trees are fast even when the number of nodes is large.

Binary trees are a common interview topic because they test multiple skills simultaneously: recursion, efficient algorithm design, and pointer manipulation. In this article, we'll explore the fundamentals of binary trees, describe common traversal techniques, and cover a few sample interview questions. By building a strong foundation, you'll be well-prepared to face a wide range of coding challenges.

Let's dive in!

Nodes, Edges, and Tree Terminology

There’s an extensive set of terms used to describe properties of binary trees. Make sure you’re familiar with these, so you’re on the same page as your interviewer when they describe the problem:

Node: A single item in a binary tree, storing a value and pointers to child nodes

Root: The topmost node of the tree, which has no parent.

Leaf: A node with no children; these appear at the bottom of the tree

Edge: The connection between two nodes.

Sibling: Nodes that share the same parent.

Subtree: Any node of the tree along with its descendants.

Trees are often measured by their height or depth — the number of levels between the root and the furthest leaf node. Depending how it’s defined, a tree with just one node might have a height of zero or one. Ask your interviewer if you’re unsure how they’re using the term.

Types of Binary Trees

Depending on their structure, some binary trees can have special names.

In a complete binary tree, every level is full except possibly the last level. The last level is filled left to right. Complete binary trees are the basis for heaps.

In a full binary tree, every node has exactly 0 children (leaf nodes) or 2 children (internal nodes). Full binary trees often come up in parsing problems.

In a perfect binary tree, no more nodes can be added without creating a new level. Perfect binary trees of height $h$ have $2^{h + 1} - 1$ nodes. Tournament brackets often resemble perfect binary trees.

In a balanced binary tree, every node’s subtrees have similar heights (usually, they differ by at most one). The balanced property ensures operations like insertion, deletion, and search are $O(\lg(n))$ .

Binary Search Trees (BST) - Special Properties and Uses

A Binary Search Tree is a specialized binary tree optimized for efficient searching operations.

In a binary tree, when looking at any node:

All nodes in the left subtree have smaller values

All nodes in the right subtree have larger values

How does this make for efficient search operations? Starting at the root node, we can compare the value of our target to the value stored in our current node. If our target is:

Larger, then it must be in the right subtree

Smaller, then it must be in the left subtree

If a binary search tree is balanced, then each time we descend into a subtree we’ll eliminate roughly half of the remaining nodes. That means our search operation will be $O(\lg(n))$ .

Some implementations of binary search trees are self-balancing, meaning their search, insert, and delete operations will always be $O(\lg(n))$ . Other implementations might not be though - in those cases, binary search trees can degenerate into a linked list, meaning search operations could be $O(n)$ . Yikes!

During a coding interview, always be explicit about your assumptions. If your input is a tree, is it a binary search tree? Is it a balanced binary search tree? Make sure you’re in alignment with your interviewer to ensure you’re solving the problem they want you to focus on.

Tree Traversal Techniques

When working with binary trees, a common operation is to visit each node exactly once to process or inspect its data. This process is known as tree traversal. Recognizing the appropriate traversal technique for a given problem is a crucial skill in coding interviews.

Because of the inherent recursive structure of trees (each node has smaller left and right subtrees), tree traversals are often implemented using recursive algorithms. Let's explore the common traversal methods.

In-order traversal

In an in-order traversal, we visit nodes in the following order:

Do an in-order traversal of the left subtree.

Visit the root node.

Do an in-order traversal of the right subtree.

Here’s the order we’d visit each node in our tree using an in-order traversal:

In-order traversal is particularly useful when working with Binary Search Trees (BSTs). Because of the BST property (smaller values in the left subtree, larger values in the right subtree), an in-order traversal will visit the nodes in ascending sorted order. This makes it useful for operations like:

Printing nodes in sorted order in a BST.

Finding the median value in a BST.

Checking if a BST is valid.

Pre-order traversal

In a pre-order traversal, we visit nodes in this order:

Visit the root node.

Do a pre-order traversal of the left subtree.

Do a pre-order traversal of the right subtree.

Here’s what that order looks like:

Pre-order traversal is often used in scenarios like:

Creating a copy of a binary tree. The root is visited first, allowing you to construct the root in the copied tree before recursively copying the subtrees.

Tree serialization. Pre-order traversal allows you to reconstruct the tree structure when combined with a way to mark null nodes.

Post-order Traversal

In a post-order traversal, the node visiting order is:

Do a post-order traversal of the left subtree.

Do a post-order traversal of the right subtree.

Visit the root node.

Going back to our sample tree, here's the order when traversing this way:

Post-order traversal is frequently employed when:

Deleting or freeing nodes in a binary tree. By processing the children first, you ensure that you don't lose access to subtree nodes when you delete the parent. This prevents memory leaks.

Calculating directory sizes in a file system (where directories can be represented as tree nodes).

Level-order Traversal (Breadth First Search)

This one is different from the others. In a level-order traversal, the tree is explored level by level, starting from the root.

Visit all nodes at the current level.

Move to the next level and repeat.

Walking our example tree one last time:

Level-order traversal is typically implemented iteratively using a queue. It's useful for:

Finding the shortest path between nodes in a tree.

Printing tree nodes level by level.

Complexity Analysis

Let's analyze the time and space complexity of these traversal techniques:

For Recursive Traversal Algorithms (In-order, Pre-order, Post-order):

Time Complexity: $O(N)$ — where $N$ is the number of nodes in the tree. In each traversal, we visit every node exactly once and perform a constant amount of work at each node (assuming each visit operation is $O(1)$ ).

Space Complexity: $O(h)$ —where $h$ is the height of the tree. The space complexity is primarily determined by the recursive call stack. In the worst case, for a skewed or unbalanced tree (e.g., a linked list-like tree), the height can be $N$ , leading to $O(N)$ space complexity. However, for a balanced binary tree, the height is approximately $\lg(N)$ resulting in $O(\lg(n))$ space complexity.

For Level-order Traversal (Breadth-First Search):

Time Complexity: $O(N)$ — similar to the recursive traversals, we visit each node once and do $O(1)$ work during the visit.

Space Complexity: $O(W)$ — where $W$ is the maximum width of the tree. In the worst-case scenario, a complete binary tree, the maximum width is approximately $N/2$ (at the last level). Therefore, the space complexity can be $O(N)$ in the worst case, as the queue might hold a significant portion of the nodes at a given level. In more sparse trees, the space complexity might be less.

Classic Binary Tree Interview Problems

Interviews often test your ability to apply traversals and tree thinking to solve specific problems. Let’s look at a few classic examples to see how the concepts discussed above come up in practice.

Validate a Binary Search Tree

Problem Statement: Given a binary tree, determine if the tree is a valid binary search tree.

General Approach: Remember that a BST has the property that for each node, all values in its left subtree are smaller than the node's value, and all values in its right subtree are larger.

For each node, we maintain a valid range of values it can take. Starting from the root, the range is initially unbounded (negative infinity to positive infinity). As we traverse down:

For the left child, the upper bound of the range becomes the current node's value.

For the right child, the lower bound of the range becomes the current node's value.

At each node, we check if the node's value falls within its allowed range. If it does, we update the range and recursively check the left and right subtrees. If not, we short circuit and return that the tree is not a BST.

Alternate Approach: Generate an in-order traversal of the tree and then check if the resulting list is in ascending order.

Edge Cases: What if the tree is empty? What if the tree contains duplicate values?

Lowest Common Ancestor

Problem Statement: Given a binary tree and two nodes (let's call them node1 and node2), find their Lowest Common Ancestor (LCA). The LCA is defined as the root of the smallest subtree that contains both node1 and node2.

General Approach: When examining a node and its subtrees, there are three possible cases:

The node is node1 or node2. In this case, we can’t descend any further, so we’ve found the lowest common ancestor.

node1 and node2 are in different subtrees: one is to the left and the other is to the right. In this case, the current node is the lowest common ancestor.

Both node1 and node2 are in the same subtree: both to the left or both to the right. Recursively call the LCA algorithm on both subtrees to find them.

Edge Cases: What happens if one of the nodes isn’t in the tree? Are there possible optimizations if we know the tree is a binary search tree? What if we could add parent pointers to the tree nodes, allowing us to walk upwards from both of the nodes?

Path Sum Problem

Problem Statement: Determine if there’s a path from the root to a leaf that sums to a target sum.

General Approach: Recursion shines here.

Base Case: If the tree is empty and our target sum is 0, then return true.

Otherwise, subtract the current node’s value from the target and recursively check for paths in both the subtrees.

Edge Cases: What if we wanted to count how many paths there were? Or, what if a path didn’t have to run from the root all the way to a leaf, but instead was any sequence of adjacent nodes?

Binary Tree Mirror

Problem Statement: Determine whether two binary trees are mirrors of each other.

General Approach: Another elegant recursive algorithm:

Check if the root nodes of both trees are equal. If not, return false.

Recursively check if:

The left subtree of the first tree is a mirror of the right subtree of the second tree, AND

The right subtree of the first tree is a mirror of the left subtree of the second tree.

Edge Case: What if we didn’t care about the values, but only wanted to check that the tree structures were mirrors of each other?

Binary Tree Problem-Solving Strategies

How to Recognize an Interview Problem is a Binary Tree Problem

Sometimes, the problem won't explicitly scream "binary tree!" You need to learn to spot the subtle clues that hint at a tree-based solution. Look for these indicators:

Hierarchical Relationships: Does the problem involve parent-child relationships or branching? Think about organizational charts, file systems, or family trees – these are naturally hierarchical. If the problem describes these kinds of relationships, consider binary trees as a potential data structure.

Recursive Structure: Binary trees are inherently recursive. If the problem can be broken down into smaller, self-similar subproblems, especially involving left and right components, it's a strong signal that a tree or recursive tree traversal is involved.

Logarithmic Complexity: If a problem explicitly asks for an $O(\lg(n))$ solution, that’s a hint that binary search trees might be involved. Most tree operations are $O(\lg(n))$ , while hash-based structures often have $O(1)$ operations and lists often have $O(1)$ or $O(n)$ operations.

Space Optimization Techniques

While binary tree operations often have logarithmic time complexity (assuming they’re balanced), space complexity can sometimes be a concern, especially with recursion. Here are a few techniques to consider for space optimization:

Iterative Traversal (for recursive traversals): While recursion is often the most natural way to implement in-order, pre-order, and post-order traversals, they can be implemented using a stack. This doesn’t change the asymptotic complexity, but it does often reduce the real amount of space used.

Morris Traversal (for in-order and pre-order): This is an advanced, constant space traversal technique for in-order and pre-order traversals. It cleverly uses the unused left and right fields of leaf nodes to create temporary links to the inorder predecessor or successor, allowing traversal without a stack or recursion. Morris traversal is an impressive technique to know, but it's very niche. Mention it to show the depth of your knowledge; few production systems actually implement it.

Prioritize clarity and correctness over premature optimization. In an interview setting, it's generally better to first implement a correct and understandable solution, even if it's not the most space-optimized. If space complexity becomes a concern or if the interviewer specifically asks about space optimization, then you can discuss or implement iterative approaches or more advanced techniques.

Common Edge Cases to Consider

Always consider these edge cases when working with trees:

Empty Tree (Null Root): The most fundamental edge case! What should your function do if the input tree has no nodes?

Single Node Tree: A tree with only a root node. Does your algorithm work correctly for a single node?

Skewed Trees (Linked List-like Trees): Unbalanced trees where all nodes are on one side (either all left children or all right children). These trees can degenerate the performance of BST operations to $O(N)$ time and space complexity. Be mindful of this worst-case scenario and consider using balanced binary trees to avoid it.

Duplicate Values (in BSTs): If you are working with Binary Search Trees, clarify with your interviewer how duplicate values should be handled. Should they be placed in the left subtree, right subtree, or are duplicates not allowed?

Conclusion: Branch Out and Conquer Tree Challenges

In this guide, we’ve covered fundamental tree concepts, traversal techniques, and worked up to complex problems and edge cases. From understanding basic terminology to tackling classic interview problems, you've built a solid foundation.

Remember, binary trees are more than just abstract concepts; they are powerful tools for representing hierarchical data and solving a wide array of computational problems. In an interview, remember to:

Embrace the recursive nature of trees: Recursion is your best friend when working with binary trees. Practice implementing recursive solutions for traversals and other tree problems.

Know your traversals: In-order, pre-order, post-order, and level-order traversals each have their strengths and applications. Understand when to use each and how to implement them both recursively and iteratively.

Recognize tree patterns: Learn to identify problems that can be solved using binary trees. Look for hierarchical relationships, recursive structures, and the need for efficient search or pathfinding in tree-like data.

Consider edge cases: Always be mindful of empty trees, single-node trees, skewed trees, and other edge cases that can trip up your algorithms.

With dedication and consistent practice, you'll be able to confidently "branch out" and conquer any binary tree problem that comes your way in your next coding interview.

Good luck!

is "superbalanced" (a new tree property we just made up).

A tree is "superbalanced" if the difference between the depths of any two leaf nodes ↴

A leaf node is a tree node with no children.

It's the "end" of a path to the bottom, from the root.

is no greater than one.

Here's a sample binary tree node class:

  class BinaryTreeNode(object):

    def __init__(self, value):
        self.value = value
        self.left  = None
        self.right = None

    def insert_left(self, value):
        self.left = BinaryTreeNode(value)
        return self.left

    def insert_right(self, value):
        self.right = BinaryTreeNode(value)
        return self.right

Gotchas

Your first thought might be to write a recursive function, thinking, "the tree is balanced if the left subtree is balanced and the right subtree is balanced." This kind of approach works well for some other tree problems.

But this isn't quite true. Counterexample: suppose that from the root of our tree:

The left subtree only has leaves at depths 10 and 11.
The right subtree only has leaves at depths 11 and 12.

Both subtrees are balanced, but from the root we will have leaves at 3 different depths.

We could instead have our recursive function get the list of distinct leaf depths for each subtree. That could work fine. But let's come up with an iterative solution instead. It's usually better to use an iterative solution instead of a recursive one because it avoids stack overflow. ↴

Overview

The call stack is what a program uses to keep track of function calls. The call stack is made up of stack frames—one for each function call.

For instance, say we called a function that rolled two dice and printed the sum.

  def roll_die():
    return random.randint(1, 6)

def roll_two_and_sum():
    total = 0
    total += roll_die()
    total += roll_die()
    print(total)

roll_two_and_sum()

First, our program calls roll_two_and_sum(). It goes on the call stack:

roll_two_and_sum()

That function calls roll_die(), which gets pushed on to the top of the call stack:

roll_die()

roll_two_and_sum()

Inside of roll_die(), we call random.randint(). Here's what our call stack looks like then:

random.randint()

roll_die()

roll_two_and_sum()

When random.randint() finishes, we return back to roll_die() by removing ("popping") random.randint()'s stack frame.

roll_die()

roll_two_and_sum()

Same thing when roll_die() returns:

roll_two_and_sum()

We're not done yet! roll_two_and_sum() calls roll_die() again:

roll_die()

roll_two_and_sum()

Which calls random.randint() again:

random.randint()

roll_die()

roll_two_and_sum()

random.randint() returns, then roll_die() returns, putting us back in roll_two_and_sum():

roll_two_and_sum()

Which calls print()():

print()()

roll_two_and_sum()

What's stored in a stack frame?

What actually goes in a function's stack frame?

A stack frame usually stores:

Local variables
Arguments passed into the function
Information about the caller's stack frame
The return address—what the program should do after the function returns (i.e.: where it should "return to"). This is usually somewhere in the middle of the caller's code.

Some of the specifics vary between processor architectures. For instance, AMD64 (64-bit x86) processors pass some arguments in registers and some on the call stack. And, ARM processors (common in phones) store the return address in a special register instead of putting it on the call stack.

The Space Cost of Stack Frames

Each function call creates its own stack frame, taking up space on the call stack. That's important because it can impact the space complexity of an algorithm. Especially when we use recursion.

For example, if we wanted to multiply all the numbers between $1$ and $n$ , we could use this recursive approach:

  def product_1_to_n(n):
    return 1 if n <= 1 else n * product_1_to_n(n - 1)

What would the call stack look like when n = 10?

First, product_1_to_n() gets called with n = 10:

    product_1_to_n()    n = 10

This calls product_1_to_n() with n = 9.

    product_1_to_n()    n = 9

    product_1_to_n()    n = 10

Which calls product_1_to_n() with n = 8.

    product_1_to_n()    n = 8

    product_1_to_n()    n = 9

    product_1_to_n()    n = 10

And so on until we get to n = 1.

    product_1_to_n()    n = 1

    product_1_to_n()    n = 2

    product_1_to_n()    n = 3

    product_1_to_n()    n = 4

    product_1_to_n()    n = 5

    product_1_to_n()    n = 6

    product_1_to_n()    n = 7

    product_1_to_n()    n = 8

    product_1_to_n()    n = 9

    product_1_to_n()    n = 10

Look at the size of all those stack frames! The entire call stack takes up $O(n)$ space. That's right—we have an $O(n)$ space cost even though our function itself doesn't create any data structures!

What if we'd used an iterative approach instead of a recursive one?

  def product_1_to_n(n):
    # We assume n >= 1
    result = 1
    for num in range(1, n + 1):
        result *= num

    return result

This version takes a constant amount of space. At the beginning of the loop, the call stack looks like this:

    product_1_to_n()    n = 10, result = 1, num = 1

As we iterate through the loop, the local variables change, but we stay in the same stack frame because we don't call any other functions.

    product_1_to_n()    n = 10, result = 2, num = 2

    product_1_to_n()    n = 10, result = 6, num = 3

    product_1_to_n()    n = 10, result = 24, num = 4

In general, even though the compiler or interpreter will take care of managing the call stack for you, it's important to consider the depth of the call stack when analyzing the space complexity of an algorithm.

Be especially careful with recursive functions! They can end up building huge call stacks.

What happens if we run out of space? It's a stack overflow! In Python 3.6, you'll get a RecursionError.

If the very last thing a function does is call another function, then its stack frame might not be needed any more. The function could free up its stack frame before doing its final call, saving space.

This is called tail call optimization (TCO). If a recursive function is optimized with TCO, then it may not end up with a big call stack.

In general, most languages don't provide TCO. Scheme is one of the few languages that guarantee tail call optimization. Some Ruby, C, and Javascript implementations may do it. Python and Java decidedly don't.

We can do this in $O(n)$ time and $O(n)$ space.

What about a tree with only one leaf node? Does your function handle that case properly?

Breakdown

Sometimes it's good to start by rephrasing or "simplifying" the problem.

The requirement of "the difference between the depths of any two leaf nodes is no greater than 1" implies that we'll have to compare the depths of all possible pairs of leaves. That'd be expensive—if there are $n$ leaves, there are $O(n^2)$ possible pairs of leaves.

But we can simplify this requirement to require less work. For example, we could equivalently say:

"The difference between the min leaf depth and the max leaf depth is 1 or less"
"There are at most two distinct leaf depths, and they are at most 1 apart"

If you're having trouble with a recursive approach, try using an iterative one.

To get to our leaves and measure their depths, we'll have to traverse the tree somehow. What methods do we know for traversing a tree?

Depth-first ↴

Depth-first search (DFS) is a method for exploring a tree or graph. In a DFS, you go as deep as possible down one path before backing up and trying a different one.

Depth-first search is like walking through a corn maze. You explore one path, hit a dead end, and go back and try a different one.

Here's a how a DFS would traverse this tree, starting with the root:

A 4-row binary tree represented by circles connected with lines. Our depth-first search has us start at the root node at the top of the tree.

We'd go down the first path we find until we hit a dead end:

The same binary tree with all nodes in the leftmost branch bolded after being visited.

Then we'd do the same thing again—go down a path until we hit a dead end:

Then we do the same thing again: head down the next leftmost path until we reach a dead end.

And again:

Until we've visited every node in the tree.

Until we reach the end.

Depth-first search is often compared with breadth-first search.

Advantages:

Depth-first search on a binary tree generally requires less memory than breadth-first.
Depth-first search can be easily implemented with recursion.

Disadvantages

A DFS doesn't necessarily find the shortest path to a node, while breadth-first search does.

and breadth-first ↴

Breadth-First Search is an algorithm that systematically explores a graph level by level. Starting from a source point, BFS visits all its immediate neighbors first, then their neighbors, and so on. This methodical approach makes it incredibly useful for finding shortest paths in unweighted graphs, exploring tree-like structures, and solving a variety of problems that come up frequently in coding interviews.

BFS is a cornerstone algorithm. It's often favored in interviews because it strikes a balance: it's conceptually straightforward to understand and implement, yet adaptable to a wide range of challenging questions.

In this article, we’ll cover core concepts of BFS, look at some implementations with time / space complexity analysis, and explore a few different problems where BFS shines. Let's dive in!

Understanding the Core Concepts of BFS

What is Breadth-First Search?

Breadth-First Search (BFS) explores a graph or tree level by level. Imagine dropping a pebble into still water: the ripples spread outwards in circles. BFS mimics this, starting at a source node and systematically visiting all nodes at the current level before moving to the next level. This level-by-level approach ensures you explore the graph in layers of "hops" from the starting point.

Starting from one point in the graph,

A 4-row binary tree represented by circles connected with lines. Our breadth-first search has us start at the root node at the top of the tree.

we look at all the nodes one level away,

The same 4-row binary tree with all nodes at depth 1 (second row) bolded after being visited.

then all the nodes two levels away,

The same 4-row binary tree with all nodes at depth 2 (third row) bolded after being visited.

then all the nodes three levels away,

The same 4-row binary tree with all nodes at depth 3 (fourth and final row) bolded after being visited.

and so on - until we’ve seen every node.

Key Data Structure: The Queue

The key behind BFS's level-by-level exploration is a queue. A queue is a First-In, First-Out (FIFO) data structure: items are added to the back and removed from the front.

In BFS, a queue stores the nodes we need to explore. When we visit a node, we add its unvisited neighbors to the back of the queue. Then, we process the next node at the front of the queue. This FIFO behavior ensures that we explore all nodes at the current "level" before moving to the next level.

The Visited Set

To prevent infinite loops and redundant processing in graphs (especially those with cycles), we need to keep track of visited nodes. This is where a visited set is essential.

Before adding a neighbor to the queue, we check if it's already in the visited set. If it is, we skip it. Otherwise, we add it to the queue and mark it as visited by adding it to the visited set. Using an efficient set data structure, these checks and inserts can be done in $O(1)$ time on average.

Path Reconstruction: The Predecessor Dictionary

In many BFS problems, especially shortest path problems, you'll need to reconstruct the path from the starting node to the target node once you find it. To do this, we use a predecessor dictionary (or parent dictionary).

As we explore the graph with BFS, whenever we enqueue a neighbor node, we record in the predecessor dictionary that we reached this neighbor from the current node. This dictionary stores each node and its immediate predecessor in the BFS traversal.

Once BFS finds the target node, we can easily reconstruct the path by starting at the target node and using the predecessor dictionary to trace back to its predecessor, then to its predecessor, and so on, until we reach the starting node. This backtracking process gives us the shortest path in reverse order, which we can then reverse to get the correct path.

Path reconstruction takes time proportional to the length of the shortest path. In the worst case, every node in the graph could be in the path, so reconstructing takes $O(V)$ overall.

The BFS Algorithm: Step-by-Step

Let's break down the BFS algorithm into clear steps:

Initialization:
- Create an empty queue, queue.
- Create an empty predecessor dictionary, predecessors
- Create an empty set, visited
- Enqueue the starting node into the queue.
- Add the starting node to visited and predecessors.
Iteration (while the queue is not empty):
- Dequeue a node from the front of the queue. Let's call this current_node.
- Process current_node. This might involve:
  - Checking if it's the target node you're searching for.
  - Performing some operation based on the node's value.
  - Simply noting that you've visited it.
- Explore Neighbors: Get all valid, unvisited neighbors of current_node.
- For each unvisited neighbor:
  - Enqueue the neighbor into the queue.
  - Add it to visited.
  - In predecessors, record that we got to this neighbor via current_node
Termination: The algorithm terminates when we reach our target node or the queue becomes empty.

At this point, you often will reconstruct the path from start_node to end_node using the predecessors dictionary.

  from collections import deque


def reconstruct_path(predecessors, start_node, end_node):
    reversed_shortest_path = []

    # Start from the end of the path and work backwards
    current_node = end_node
    while current_node:
        reversed_shortest_path.append(current_node)
        current_node = predecessors[current_node]

    # Reverse our path to get the right order
    reversed_shortest_path.reverse()  # flip it around, in place
    return reversed_shortest_path  # no longer reversed


def bfs_get_path(graph, start_node, end_node):
    if start_node not in graph:
        raise Exception('Start node not in graph')
    if end_node not in graph:
        raise Exception('End node not in graph')

    queue = deque()
    queue.append(start_node)

    visited = set([start_node])

    predecessors = {start_node: None}

    while len(queue) > 0:
        current_node = queue.popleft()

        # Stop when we reach the end node
        if current_node == end_node:
            return reconstruct_path(predecessors, start_node, end_node)

        for neighbor in graph[current_node]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)
                predecessors[neighbor] = current_node

    # If we get here, then we never found the end node
    # so there's NO path from start_node to end_node
    return None

Analyzing Time and Space Complexity of BFS

Once you’ve coded up an algorithm, interviewers are going to ask you to analyze its time and space complexity.

Time Complexity: $O(V+E)$

$V$ is the number of vertices (nodes) and $E$ is the number of edges in the graph. We visit each vertex at most once (due to the visited set). For each vertex, we iterate through its neighbors. In total, across all vertices, we examine each edge at most twice (once for the node on each end). Putting it all together, we’ve got $O(V+E)$ time complexity.

Space Complexity: $O(V)$

$V$ is the number of vertices. Our three data structures are the node queue, the visited set, and the backtracking dictionary. Because each node gets added to the queue exactly once, the queue won’t grow beyond $O(V)$ . Our visited set also grows to hold all the nodes, $O(V)$ size. Finally, our backtracking dictionary has one entry per node, so it’s $O(V)$ , too. Putting these together, we’re still $O(V)$ space.

Applications of BFS: Where is BFS Useful?

Because of its versatility, BFS shows up in a lot of places. Look for these problem structures that suggest BFS is the appropriate algorithm:

Problems where you’re exploring a set of states and have to find the shortest sequence from one state to another.
Problems involving grid-based structures (mazes, grids, etc.) where each step has the same cost.
Problems where you need to look at connected items (friends in a social network, links within a website, railroads between cities, etc.).

When approaching a problem that might be solved with BFS, consider these steps:

Identify BFS Applicability: Does the problem involve finding the shortest path in an unweighted graph, exploring levels or layers, or searching connected components? If so, BFS might be a good fit.
Define the Graph/States: What are the "nodes" in your problem? How are they connected (what are the "edges" or transitions)? This could be explicit graph nodes, grid cells, words in a word ladder, etc.
Define Start and End: What is the starting node(s)? Is there a specific target node or condition you are searching for?
Define Neighbors: How do you find the valid neighbors of a node? Consider constraints (walls in a maze, valid word transformations, etc.).
Handle Boundary Conditions: Consider edge cases like empty inputs, disconnected components, and whether BFS is feasible given the input size.

Sample BFS Interview Questions

Here are some common interview problems where a BFS-style algorithm could work:

Binary Tree Level Order Traversal

Problem Description: Given a binary tree, return its node values in level order traversal. That is, nodes at each level are visited from left to right, level by level.

Applying BFS:

Our starting node is the root of the binary tree. We don't have a specific ending node; we'll continue until the queue is empty.
Each node's neighbors are their left and right children (if they have them).
We can check for an empty tree (comparing the root node to None). And, assuming the tree is a reasonable size, BFS should be feasible.

Shortest Path Through a Maze

Problem Description: Given an ASCII maze where each step has the same cost, find the shortest path from the top left to the bottom right.

  .#######             @####### 
..#.#..#             @@#.#..#
#.....##             #@@@@@##
###.#..#      ==>    ###.#@.#
#...#.##             #...#@##
#.###.#.             #.###@#.
#.....##             #....@##
#####...             #####@@@

Applying BFS:

Our starting node is the top left corner. Our ending node is the bottom right corner.
Each node's neighbors are the points above, below, left, and right - as long as they're not walls. We need to be careful of boundary conditions, like nodes on the edges of the grid.
We can check for edge cases like the start or end position being a wall or mazes where there's no path from the start to the finish.
If the maze is very large, it's possible BFS will be too slow or require too much memory. Ask your interviewer how large the maze is expected to be!

Number of Islands

Problem Description: Given a 2D grid indicating land and water, count the number of islands.

Applying BFS:

Start with a set of visited nodes, initially empty.
Iterate through the entire grid. When we reach a point that's an island:
- If the point is already visited, do nothing.
- Otherwise, increase our count by 1 and do BFS from that point outwards. Each BFS visits all the points on a single island. A point's neighbors are adjacent points that are also land.
Return the total number of islands seen.

Word Ladder

Problem Description: Given a start word and a target word, find the fewest steps required to transform one into the other, changing only one letter at a time.

As an example, to transform head into tail, we could generate this sequence:

head
heal
teal
tell
tall
tail

Applying BFS:

Our starting node is the start word. Our ending node is the target word.
Each node's neighbors are words that differ by one letter. As an example, some neighboring words for node would be:
- code
- mode
- nods
- note
- rode
- ...
We should check for edge cases like:
- The start or target not being valid words
- The start and target being different lengths
- No possible word ladder

Conclusion: BFS - A Powerful Tool in Your Interview Toolkit

Breadth-First Search is an indispensable algorithm in your coding interview toolkit. Its systematic level-by-level exploration makes it a powerful and efficient approach for a wide range of problems. By mastering the core concepts – the queue, visited set, predecessor dictionary – and practicing its implementation, you'll be well-prepared to confidently tackle BFS-related interview questions.

Remember to:

Practice recognizing problems where BFS could be used.
Clearly articulate your BFS approach during interviews, highlighting how you are defining nodes, neighbors, and handling visited states.
Understand and be able to explain the time and space complexity for different BFS variants.

With practice and a solid understanding of BFS, you'll be ready to impress in your next coding interview! Good luck!

are common ways to traverse a tree. Which one should we use here?

The worst-case time and space costs of both are the same—you could make a case for either.

But one characteristic of our algorithm is that it could short-circuit and return False as soon as it finds two leaves with depths more than 1 apart. So maybe we should use a traversal that will hit leaves as quickly as possible...

Depth-first traversal will generally hit leaves before breadth-first, so let's go with that. How could we write a depth-first walk that also keeps track of our depth?

Solution

We do a depth-first walk ↴

Depth-first search (DFS) is a method for exploring a tree or graph. In a DFS, you go as deep as possible down one path before backing up and trying a different one.

Depth-first search is like walking through a corn maze. You explore one path, hit a dead end, and go back and try a different one.

Here's a how a DFS would traverse this tree, starting with the root:

We'd go down the first path we find until we hit a dead end:

Then we'd do the same thing again—go down a path until we hit a dead end:

And again:

Until we reach the end.

Depth-first search is often compared with breadth-first search.

Advantages:

Depth-first search on a binary tree generally requires less memory than breadth-first.
Depth-first search can be easily implemented with recursion.

Disadvantages

A DFS doesn't necessarily find the shortest path to a node, while breadth-first search does.

through our tree, keeping track of the depth as we go. When we find a leaf, we add its depth to a list of depths if we haven't seen that depth already.

Each time we hit a leaf with a new depth, there are two ways that our tree might now be unbalanced:

There are more than 2 different leaf depths
There are exactly 2 leaf depths and they are more than 1 apart.

Why are we doing a depth-first walk and not a breadth-first ↴

In this article, we’ll cover core concepts of BFS, look at some implementations with time / space complexity analysis, and explore a few different problems where BFS shines. Let's dive in!

Understanding the Core Concepts of BFS

What is Breadth-First Search?

Starting from one point in the graph,

we look at all the nodes one level away,

then all the nodes two levels away,

then all the nodes three levels away,

and so on - until we’ve seen every node.

Key Data Structure: The Queue

The key behind BFS's level-by-level exploration is a queue. A queue is a First-In, First-Out (FIFO) data structure: items are added to the back and removed from the front.

The Visited Set

To prevent infinite loops and redundant processing in graphs (especially those with cycles), we need to keep track of visited nodes. This is where a visited set is essential.

Path Reconstruction: The Predecessor Dictionary

Path reconstruction takes time proportional to the length of the shortest path. In the worst case, every node in the graph could be in the path, so reconstructing takes $O(V)$ overall.

The BFS Algorithm: Step-by-Step

Let's break down the BFS algorithm into clear steps:

Initialization:
- Create an empty queue, queue.
- Create an empty predecessor dictionary, predecessors
- Create an empty set, visited
- Enqueue the starting node into the queue.
- Add the starting node to visited and predecessors.
Iteration (while the queue is not empty):
- Dequeue a node from the front of the queue. Let's call this current_node.
- Process current_node. This might involve:
  - Checking if it's the target node you're searching for.
  - Performing some operation based on the node's value.
  - Simply noting that you've visited it.
- Explore Neighbors: Get all valid, unvisited neighbors of current_node.
- For each unvisited neighbor:
  - Enqueue the neighbor into the queue.
  - Add it to visited.
  - In predecessors, record that we got to this neighbor via current_node
Termination: The algorithm terminates when we reach our target node or the queue becomes empty.

At this point, you often will reconstruct the path from start_node to end_node using the predecessors dictionary.

  from collections import deque


def reconstruct_path(predecessors, start_node, end_node):
    reversed_shortest_path = []

    # Start from the end of the path and work backwards
    current_node = end_node
    while current_node:
        reversed_shortest_path.append(current_node)
        current_node = predecessors[current_node]

    # Reverse our path to get the right order
    reversed_shortest_path.reverse()  # flip it around, in place
    return reversed_shortest_path  # no longer reversed


def bfs_get_path(graph, start_node, end_node):
    if start_node not in graph:
        raise Exception('Start node not in graph')
    if end_node not in graph:
        raise Exception('End node not in graph')

    queue = deque()
    queue.append(start_node)

    visited = set([start_node])

    predecessors = {start_node: None}

    while len(queue) > 0:
        current_node = queue.popleft()

        # Stop when we reach the end node
        if current_node == end_node:
            return reconstruct_path(predecessors, start_node, end_node)

        for neighbor in graph[current_node]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)
                predecessors[neighbor] = current_node

    # If we get here, then we never found the end node
    # so there's NO path from start_node to end_node
    return None

Analyzing Time and Space Complexity of BFS

Once you’ve coded up an algorithm, interviewers are going to ask you to analyze its time and space complexity.

Time Complexity: $O(V+E)$

Space Complexity: $O(V)$

Applications of BFS: Where is BFS Useful?

Because of its versatility, BFS shows up in a lot of places. Look for these problem structures that suggest BFS is the appropriate algorithm:

Problems where you’re exploring a set of states and have to find the shortest sequence from one state to another.
Problems involving grid-based structures (mazes, grids, etc.) where each step has the same cost.
Problems where you need to look at connected items (friends in a social network, links within a website, railroads between cities, etc.).

When approaching a problem that might be solved with BFS, consider these steps:

Identify BFS Applicability: Does the problem involve finding the shortest path in an unweighted graph, exploring levels or layers, or searching connected components? If so, BFS might be a good fit.
Define the Graph/States: What are the "nodes" in your problem? How are they connected (what are the "edges" or transitions)? This could be explicit graph nodes, grid cells, words in a word ladder, etc.
Define Start and End: What is the starting node(s)? Is there a specific target node or condition you are searching for?
Define Neighbors: How do you find the valid neighbors of a node? Consider constraints (walls in a maze, valid word transformations, etc.).
Handle Boundary Conditions: Consider edge cases like empty inputs, disconnected components, and whether BFS is feasible given the input size.

Sample BFS Interview Questions

Here are some common interview problems where a BFS-style algorithm could work:

Binary Tree Level Order Traversal

Problem Description: Given a binary tree, return its node values in level order traversal. That is, nodes at each level are visited from left to right, level by level.

Applying BFS:

Our starting node is the root of the binary tree. We don't have a specific ending node; we'll continue until the queue is empty.
Each node's neighbors are their left and right children (if they have them).
We can check for an empty tree (comparing the root node to None). And, assuming the tree is a reasonable size, BFS should be feasible.

Shortest Path Through a Maze

Problem Description: Given an ASCII maze where each step has the same cost, find the shortest path from the top left to the bottom right.

  .#######             @####### 
..#.#..#             @@#.#..#
#.....##             #@@@@@##
###.#..#      ==>    ###.#@.#
#...#.##             #...#@##
#.###.#.             #.###@#.
#.....##             #....@##
#####...             #####@@@

Applying BFS:

Our starting node is the top left corner. Our ending node is the bottom right corner.
Each node's neighbors are the points above, below, left, and right - as long as they're not walls. We need to be careful of boundary conditions, like nodes on the edges of the grid.
We can check for edge cases like the start or end position being a wall or mazes where there's no path from the start to the finish.
If the maze is very large, it's possible BFS will be too slow or require too much memory. Ask your interviewer how large the maze is expected to be!

Number of Islands

Problem Description: Given a 2D grid indicating land and water, count the number of islands.

Applying BFS:

Start with a set of visited nodes, initially empty.
Iterate through the entire grid. When we reach a point that's an island:
- If the point is already visited, do nothing.
- Otherwise, increase our count by 1 and do BFS from that point outwards. Each BFS visits all the points on a single island. A point's neighbors are adjacent points that are also land.
Return the total number of islands seen.

Word Ladder

Problem Description: Given a start word and a target word, find the fewest steps required to transform one into the other, changing only one letter at a time.

As an example, to transform head into tail, we could generate this sequence:

head
heal
teal
tell
tall
tail

Applying BFS:

Our starting node is the start word. Our ending node is the target word.
Each node's neighbors are words that differ by one letter. As an example, some neighboring words for node would be:
- code
- mode
- nods
- note
- rode
- ...
We should check for edge cases like:
- The start or target not being valid words
- The start and target being different lengths
- No possible word ladder

Conclusion: BFS - A Powerful Tool in Your Interview Toolkit

Remember to:

Practice recognizing problems where BFS could be used.
Clearly articulate your BFS approach during interviews, highlighting how you are defining nodes, neighbors, and handling visited states.
Understand and be able to explain the time and space complexity for different BFS variants.

With practice and a solid understanding of BFS, you'll be ready to impress in your next coding interview! Good luck!

one? You could make a case for either. We chose depth-first because it reaches leaves faster, which allows us to short-circuit earlier in some cases.

  def is_balanced(tree_root):

    # A tree with no nodes is superbalanced, since there are no leaves!
    if tree_root is None:
        return True

    # We short-circuit as soon as we find more than 2
    depths = []

    # We'll treat this list as a stack that will store tuples of (node, depth)
    nodes = []
    nodes.append((tree_root, 0))

    while len(nodes):
        # Pop a node and its depth from the top of our stack
        node, depth = nodes.pop()

        # Case: we found a leaf
        if (not node.left) and (not node.right):
            # We only care if it's a new depth
            if depth not in depths:
                depths.append(depth)

                # Two ways we might now have an unbalanced tree:
                #   1) more than 2 different leaf depths
                #   2) 2 leaf depths that are more than 1 apart
                if ((len(depths) > 2) or
                        (len(depths) == 2 and abs(depths[0] - depths[1]) > 1)):
                    return False
        else:
            # Case: this isn't a leaf - keep stepping down
            if node.left:
                nodes.append((node.left, depth + 1))
            if node.right:
                nodes.append((node.right, depth + 1))

    return True

Complexity

$O(n)$ time and $O(n)$ space.

For time, the worst case is the tree is balanced and we have to iterate over all $n$ nodes to make sure.

For the space cost, we have two data structures to watch: depths and nodes.

depths will never hold more than three elements, so we can write that off as $O(1)$ .

Because we’re doing a depth first search, nodes will hold at most $d$ nodes where $d$ is the depth of the tree (the number of levels in the tree from the root node down to the lowest node). So we could say our space cost is $O(d)$ .

But we can also relate $d$ to $n$ . In a balanced tree, $d$ is $O(\log_{2}(n))$ . And the more unbalanced the tree gets, the closer $d$ gets to $n$ .

In the worst case, the tree is a straight line of right children from the root where every node in that line also has a left child. The traversal will walk down the line of right children, adding a new left child to nodes at each step. When the traversal hits the rightmost node, nodes will hold half of the $n$ total nodes in the tree. Half $n$ is $O(n)$ , so our worst case space cost is $O(n)$ .

What We Learned

This is an intro to some tree basics. If this is new to you, don't worry—it can take a few questions for this stuff to come together. We have a few more coming up.

Particular things to note:

Focus on depth-first ↴

Depth-first search (DFS) is a method for exploring a tree or graph. In a DFS, you go as deep as possible down one path before backing up and trying a different one.

Depth-first search is like walking through a corn maze. You explore one path, hit a dead end, and go back and try a different one.

Here's a how a DFS would traverse this tree, starting with the root:

We'd go down the first path we find until we hit a dead end:

Then we'd do the same thing again—go down a path until we hit a dead end:

And again:

And again:

Until we reach the end.

Depth-first search is often compared with breadth-first search.

Advantages:

Depth-first search on a binary tree generally requires less memory than breadth-first.

Depth-first search can be easily implemented with recursion.

Disadvantages

A DFS doesn't necessarily find the shortest path to a node, while breadth-first search does.

vs breadth-first ↴

Breadth-First Search is an algorithm that systematically explores a graph level by level. Starting from a source point, BFS visits all its immediate neighbors first, then their neighbors, and so on. This methodical approach makes it incredibly useful for finding shortest paths in unweighted graphs, exploring tree-like structures, and solving a variety of problems that come up frequently in coding interviews.

BFS is a cornerstone algorithm. It's often favored in interviews because it strikes a balance: it's conceptually straightforward to understand and implement, yet adaptable to a wide range of challenging questions.

In this article, we’ll cover core concepts of BFS, look at some implementations with time / space complexity analysis, and explore a few different problems where BFS shines. Let's dive in!

Understanding the Core Concepts of BFS

What is Breadth-First Search?

Breadth-First Search (BFS) explores a graph or tree level by level. Imagine dropping a pebble into still water: the ripples spread outwards in circles. BFS mimics this, starting at a source node and systematically visiting all nodes at the current level before moving to the next level. This level-by-level approach ensures you explore the graph in layers of "hops" from the starting point.

Starting from one point in the graph,

we look at all the nodes one level away,

then all the nodes two levels away,

then all the nodes three levels away,

and so on - until we’ve seen every node.

Key Data Structure: The Queue

The key behind BFS's level-by-level exploration is a queue. A queue is a First-In, First-Out (FIFO) data structure: items are added to the back and removed from the front.

In BFS, a queue stores the nodes we need to explore. When we visit a node, we add its unvisited neighbors to the back of the queue. Then, we process the next node at the front of the queue. This FIFO behavior ensures that we explore all nodes at the current "level" before moving to the next level.

The Visited Set

To prevent infinite loops and redundant processing in graphs (especially those with cycles), we need to keep track of visited nodes. This is where a visited set is essential.

Before adding a neighbor to the queue, we check if it's already in the visited set. If it is, we skip it. Otherwise, we add it to the queue and mark it as visited by adding it to the visited set. Using an efficient set data structure, these checks and inserts can be done in $O(1)$ time on average.

Path Reconstruction: The Predecessor Dictionary

In many BFS problems, especially shortest path problems, you'll need to reconstruct the path from the starting node to the target node once you find it. To do this, we use a predecessor dictionary (or parent dictionary).

As we explore the graph with BFS, whenever we enqueue a neighbor node, we record in the predecessor dictionary that we reached this neighbor from the current node. This dictionary stores each node and its immediate predecessor in the BFS traversal.

Once BFS finds the target node, we can easily reconstruct the path by starting at the target node and using the predecessor dictionary to trace back to its predecessor, then to its predecessor, and so on, until we reach the starting node. This backtracking process gives us the shortest path in reverse order, which we can then reverse to get the correct path.

Path reconstruction takes time proportional to the length of the shortest path. In the worst case, every node in the graph could be in the path, so reconstructing takes $O(V)$ overall.

The BFS Algorithm: Step-by-Step

Let's break down the BFS algorithm into clear steps:

Initialization:

Create an empty queue, queue.

Create an empty predecessor dictionary, predecessors

Create an empty set, visited

Enqueue the starting node into the queue.

Add the starting node to visited and predecessors.

Iteration (while the queue is not empty):

Dequeue a node from the front of the queue. Let's call this current_node.

Process current_node. This might involve:

Checking if it's the target node you're searching for.

Performing some operation based on the node's value.

Simply noting that you've visited it.

Explore Neighbors: Get all valid, unvisited neighbors of current_node.

For each unvisited neighbor:

Enqueue the neighbor into the queue.

Add it to visited.

In predecessors, record that we got to this neighbor via current_node

Termination: The algorithm terminates when we reach our target node or the queue becomes empty.

At this point, you often will reconstruct the path from start_node to end_node using the predecessors dictionary.

from collections import deque def reconstruct_path(predecessors, start_node, end_node): reversed_shortest_path = [] # Start from the end of the path and work backwards current_node = end_node while current_node: reversed_shortest_path.append(current_node) current_node = predecessors[current_node] # Reverse our path to get the right order reversed_shortest_path.reverse() # flip it around, in place return reversed_shortest_path # no longer reversed def bfs_get_path(graph, start_node, end_node): if start_node not in graph: raise Exception('Start node not in graph') if end_node not in graph: raise Exception('End node not in graph') queue = deque() queue.append(start_node) visited = set([start_node]) predecessors = {start_node: None} while len(queue) > 0: current_node = queue.popleft() # Stop when we reach the end node if current_node == end_node: return reconstruct_path(predecessors, start_node, end_node) for neighbor in graph[current_node]: if neighbor not in visited: queue.append(neighbor) visited.add(neighbor) predecessors[neighbor] = current_node # If we get here, then we never found the end node # so there's NO path from start_node to end_node return None

Analyzing Time and Space Complexity of BFS

Once you’ve coded up an algorithm, interviewers are going to ask you to analyze its time and space complexity.

Time Complexity: $O(V+E)$

$V$ is the number of vertices (nodes) and $E$ is the number of edges in the graph. We visit each vertex at most once (due to the visited set). For each vertex, we iterate through its neighbors. In total, across all vertices, we examine each edge at most twice (once for the node on each end). Putting it all together, we’ve got $O(V+E)$ time complexity.

Space Complexity: $O(V)$

$V$ is the number of vertices. Our three data structures are the node queue, the visited set, and the backtracking dictionary. Because each node gets added to the queue exactly once, the queue won’t grow beyond $O(V)$ . Our visited set also grows to hold all the nodes, $O(V)$ size. Finally, our backtracking dictionary has one entry per node, so it’s $O(V)$ , too. Putting these together, we’re still $O(V)$ space.

Applications of BFS: Where is BFS Useful?

Because of its versatility, BFS shows up in a lot of places. Look for these problem structures that suggest BFS is the appropriate algorithm:

Problems where you’re exploring a set of states and have to find the shortest sequence from one state to another.

Problems involving grid-based structures (mazes, grids, etc.) where each step has the same cost.

Problems where you need to look at connected items (friends in a social network, links within a website, railroads between cities, etc.).

When approaching a problem that might be solved with BFS, consider these steps:

Identify BFS Applicability: Does the problem involve finding the shortest path in an unweighted graph, exploring levels or layers, or searching connected components? If so, BFS might be a good fit.

Define the Graph/States: What are the "nodes" in your problem? How are they connected (what are the "edges" or transitions)? This could be explicit graph nodes, grid cells, words in a word ladder, etc.

Define Start and End: What is the starting node(s)? Is there a specific target node or condition you are searching for?

Define Neighbors: How do you find the valid neighbors of a node? Consider constraints (walls in a maze, valid word transformations, etc.).

Handle Boundary Conditions: Consider edge cases like empty inputs, disconnected components, and whether BFS is feasible given the input size.

Sample BFS Interview Questions

Here are some common interview problems where a BFS-style algorithm could work:

Binary Tree Level Order Traversal

Problem Description: Given a binary tree, return its node values in level order traversal. That is, nodes at each level are visited from left to right, level by level.

Applying BFS:

Our starting node is the root of the binary tree. We don't have a specific ending node; we'll continue until the queue is empty.

Each node's neighbors are their left and right children (if they have them).

We can check for an empty tree (comparing the root node to None). And, assuming the tree is a reasonable size, BFS should be feasible.

Shortest Path Through a Maze

Problem Description: Given an ASCII maze where each step has the same cost, find the shortest path from the top left to the bottom right.

.####### @####### ..#.#..# @@#.#..# #.....## #@@@@@## ###.#..# ==> ###.#@.# #...#.## #...#@## #.###.#. #.###@#. #.....## #....@## #####... #####@@@

Applying BFS:

Our starting node is the top left corner. Our ending node is the bottom right corner.

Each node's neighbors are the points above, below, left, and right - as long as they're not walls. We need to be careful of boundary conditions, like nodes on the edges of the grid.

We can check for edge cases like the start or end position being a wall or mazes where there's no path from the start to the finish.

If the maze is very large, it's possible BFS will be too slow or require too much memory. Ask your interviewer how large the maze is expected to be!

Number of Islands

Problem Description: Given a 2D grid indicating land and water, count the number of islands.

Applying BFS:

Start with a set of visited nodes, initially empty.

Iterate through the entire grid. When we reach a point that's an island:

If the point is already visited, do nothing.

Otherwise, increase our count by 1 and do BFS from that point outwards. Each BFS visits all the points on a single island. A point's neighbors are adjacent points that are also land.

Return the total number of islands seen.

Word Ladder

Problem Description: Given a start word and a target word, find the fewest steps required to transform one into the other, changing only one letter at a time.

As an example, to transform head into tail, we could generate this sequence:

head

heal

teal

tell

tall

tail

Applying BFS:

Our starting node is the start word. Our ending node is the target word.

Each node's neighbors are words that differ by one letter. As an example, some neighboring words for node would be:

code

mode

nods

note

rode

...

We should check for edge cases like:

The start or target not being valid words

The start and target being different lengths

No possible word ladder

Conclusion: BFS - A Powerful Tool in Your Interview Toolkit

Breadth-First Search is an indispensable algorithm in your coding interview toolkit. Its systematic level-by-level exploration makes it a powerful and efficient approach for a wide range of problems. By mastering the core concepts – the queue, visited set, predecessor dictionary – and practicing its implementation, you'll be well-prepared to confidently tackle BFS-related interview questions.

Remember to:

Practice recognizing problems where BFS could be used.

Clearly articulate your BFS approach during interviews, highlighting how you are defining nodes, neighbors, and handling visited states.

Understand and be able to explain the time and space complexity for different BFS variants.

With practice and a solid understanding of BFS, you'll be ready to impress in your next coding interview! Good luck!

traversal. You should be very comfortable with the differences between the two and the strengths and weaknesses of each.

You should also be very comfortable coding each of them up.

One tip: Remember that breadth-first uses a queue ↴

Quick reference

Worst Case

space $O(n)$

enqueue $O(1)$

dequeue $O(1)$

peek $O(1)$

A queue stores items in a first-in, first-out (FIFO) order.

Picture a queue like the line outside a busy restaurant. First come, first served.

Strengths:

Fast operations. All queue operations take $O(1)$ time.

Uses

Breadth-first search uses a queue to keep track of the nodes to visit next.

Printers use queues to manage jobs—jobs get printed in the order they're submitted.

Web servers use queues to manage requests—page requests get fulfilled in the order they're received.

Processes wait in the CPU scheduler's queue for their turn to run.

Implementation

Queues are easy to implement with linked lists:

To enqueue, insert at the tail of the linked list.

To dequeue, remove at the head of the linked list.

You could implement a queue with an array or dynamic array, but it would get kinda messy. Try drawing it out. You'll notice that you'd need to build out a "scoot over" or "re-center" operation that automatically fires when your queue items hit the bottom edge of the array.

	Worst Case
space	$O(n)$
enqueue	$O(1)$
dequeue	$O(1)$
peek	$O(1)$

	Worst Case
space	$O(n)$
push	$O(1)$
pop	$O(1)$
peek	$O(1)$

	Stack Push	Stack Pop
Linked Lists	insert at head	remove at head
Dynamic Arrays	append	remove last element

and depth-first uses a stack ↴

Quick reference

Worst Case

space $O(n)$

push $O(1)$

pop $O(1)$

peek $O(1)$

A stack stores items in a last-in, first-out (LIFO) order.

Picture a pile of dirty plates in your sink. As you add more plates, you bury the old ones further down. When you take a plate off the top to wash it, you're taking the last plate you put in. "Last in, first out."

Strengths:

Fast operations. All stack operations take $O(1)$ time.

Uses:

The call stack is a stack that tracks function calls in a program. When a function returns, which function do we "pop" back to? The last one that "pushed" a function call.

Depth-first search uses a stack (sometimes the call stack) to keep track of which nodes to visit next.

String parsing—stacks turn out to be useful for several types of string parsing.

Implementation

You can implement a stack with either a linked list or a dynamic array—they both work pretty well:

Stack Push Stack Pop

Linked Lists insert at head remove at head

Dynamic Arrays append remove last element

(could be the call stack or an actual stack object). That's not just a clue about implementation, it also helps with figuring out the differences in behavior. Those differences come from whether we visit nodes in the order we see them (first in, first out) or we visit the last-seen node first (last in, first out).

Do you have an answer?

Show answer

I have an answer Tell me more

Wanna review this one again later? Or do you feel like you got it all?

Mark as done Pin for review later