DSA Visualizations | Hello Interview

Fundamentals

BFS is a level-by-level traversal algorithm. It starts at the root node of the binary tree and visits all nodes at the current level before moving to the next level of the tree.


def bfs(root):
  if not root:
    return []

  result = []
  queue = deque([root])

  while queue:
    curr_node = queue.popleft()
    result.append(curr_node.val)
    
    if curr_node.left:
      queue.append(curr_node.left)
    if curr_node.right:
      queue.append(curr_node.right)

  return result

breadth-first search

0 / 15

The order in which BFS visits the nodes in a binary tree.

BFS Procedure

BFS uses a queue to keep track of the nodes it needs to visit, and follows these steps:

Start at the root node and add it to the queue.
While the queue is not empty, remove the node at the front of the queue and visit it.
Add the children of the node to the back queue.
Repeat steps 2 and 3 until the queue is empty, which means you've processed all nodes in the tree.

Queues in Python

In Python, you can use the deque class from the collections module to create a queue.

The deque class provides an append method to add elements to the end of the queue and a popleft method to remove elements from the front of the queue, both of which run in O(1) time.

Implementation

Below is a basic implementation of BFS on a binary tree. The result list stores the nodes in the order in which they are visited.


def bfs(root):
  if not root:
    return []

  result = []
  queue = deque([root])

  while queue:
    curr_node = queue.popleft()
    result.append(curr_node.val)
    
    if curr_node.left:
      queue.append(curr_node.left)
    if curr_node.right:
      queue.append(curr_node.right)

  return result

breadth-first search

0 / 15

Summary

BFS is a traversal algorithm that visits all nodes at a particular level before moving to the next level.
BFS uses a queue to keep track of the nodes it needs to visit.

Processing Levels

The distinguishing feature of BFS is that it visits all nodes at a particular level before moving onto the nodes at the next level.

Compared to depth-first search, BFS makes it much easier to tell when we have finished processing all nodes at a particular level. This makes it a natural candidate for questions that ask something about the nodes at each level, which is shown below in the Level-Order Traversal algorithm.

DESCRIPTION

Given a binary tree, return the level-order traversal of its nodes' values. (i.e., from left to right, level by level).

Input

Output [[4], [2, 7], [1, 3, 6, 9]]

We can extend our basic BFS algorithm to calculate the number of nodes at each level by adding a for-loop that iterates over the size of the queue at the beginning of each level.

Each time the for-loop runs, we add the current node to the current_level list.
When the for-loop finishes, we have finished processing all nodes at that level, and we can add the current_level list to the result list. We can reset the current_level list to an empty list to prepare for the next level.

from collections import deque
    
def level_order(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        # number of nodes at the current level
        level_size = len(queue)
        current_level = []
        
        for _ in range(level_size):
            curr = queue.popleft()
            current_level.append(curr.val)
            
            if curr.left:
                queue.append(curr.left)
            if curr.right:
                queue.append(curr.right)
        
        # IMPORTANT
        # we have finished processing all nodes at the current level
        result.append(current_level)
        
    return result

To help you visualize how this algorithm works, the diagram below shows the state of the queue after we have finished processing the 2nd level of the tree.

Notice that queue contains the nodes at the 3rd level of the tree, [1, 3, 6, 9]. When we enter the next iteration of the while loop, the for loop will run 4 times to process these nodes.


from collections import deque
    
def level_order(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        # number of nodes at current level
        level_size = len(queue)
        current_level = []
        
        for _ in range(level_size):
            curr = queue.popleft()
            current_level.append(curr.val)
            
            if curr.left:
                queue.append(curr.left)
            if curr.right:
                queue.append(curr.right)
        
        # IMPORTANT
        # we have finished processing all
        # nodes at the current level
        result.append(current_level)
        
    return result

The state of the aglorithm after we have finished processing the nodes at the 2nd level of the tree.

Using a for-loop to iterate over the nodes at each level is such a common pattern that it is the verison of BFS on binary trees you need to know for interviews. The practice problems we will look at next all use this version of BFS.

Complexity Analysis

The base complexity of BFS is:

Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node exactly once. Space Complexity: O(N), where N is the number of nodes in the tree. The space complexity is determined by the size of the queue, which can grow up to N/2 in the worst case (the last level of a full binary tree).

Next: Level Order Sum

Your account is free and you can post anonymously if you choose.

Loading comments...

Back to Home

Eliminating Pairs

Overview

Container With Most Water

3-Sum

Triangle Numbers

Pointers as Regions

Move Zeroes

Sort Colors

Trapping Rain Water

Variable-Length

Overview

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Fixed-Length

Overview

Maximum Sum of Subarrays of Size K

Max Points You Can Obtain From Cards

Max Sum of Distinct Subarrays Length k

Overview

Can Attend Meetings

Insert Interval

Non-Overlapping Intervals

Merge Intervals

Employee Free Time

Overview

Valid Parentheses

Decode String

Longest Valid Parentheses

Monotonic Stack

Overview

Daily Temperatures

Largest Rectangle in Histogram

Overview

Linked List Cycle

Palindrome Linked List

Remove Nth Node From End of List

Reorder List

Swap Nodes in Pairs

Overview

Apple Harvest (Koko Eating Bananas)

Search in Rotated Sorted Array

Overview

Kth Largest Element in an Array

K Closest Points to Origin

Find K Closest Elements

Merge K Sorted Lists

Introduction

Binary Trees

Overview

Level Order Sum

Rightmost Node

Zigzag Level Order

Maximum Width of Binary Tree

Graphs

Overview

Minimum Knight Moves

Rotting Oranges

01-Matrix

Bus Routes

Overview

Word Search

Solution Space Trees

Subsets

Generate Parentheses

Combination Sum

Topological Sort

Overview

Course Schedule

Course Schedule II

Fundamentals

Solving a Question with Dynamic Programming

Counting Bits

Decode Ways

Maximal Square

Unique Paths

Longest Increasing Subsequence

Word Break

Maximum Profit in Job Scheduling

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Overview

Implement Trie Methods

Prefix Matching

Overview

Count Vowels in Substrings

Subarray Sum Equals K

Spiral Matrix

Rotate Image

Set Matrix Zeroes

Introduction

Level Order Sum

Fundamentals

BFS is a level-by-level traversal algorithm. It starts at the root node of the binary tree and visits all nodes at the current level before moving to the next level of the tree.


def bfs(root):
  if not root:
    return []

  result = []
  queue = deque([root])

  while queue:
    curr_node = queue.popleft()
    result.append(curr_node.val)
    
    if curr_node.left:
      queue.append(curr_node.left)
    if curr_node.right:
      queue.append(curr_node.right)

  return result

breadth-first search

0 / 15

The order in which BFS visits the nodes in a binary tree.

BFS Procedure

BFS uses a queue to keep track of the nodes it needs to visit, and follows these steps:

Start at the root node and add it to the queue.
While the queue is not empty, remove the node at the front of the queue and visit it.
Add the children of the node to the back queue.
Repeat steps 2 and 3 until the queue is empty, which means you've processed all nodes in the tree.

Queues in Python

In Python, you can use the deque class from the collections module to create a queue.

The deque class provides an append method to add elements to the end of the queue and a popleft method to remove elements from the front of the queue, both of which run in O(1) time.

Implementation

Below is a basic implementation of BFS on a binary tree. The result list stores the nodes in the order in which they are visited.


def bfs(root):
  if not root:
    return []

  result = []
  queue = deque([root])

  while queue:
    curr_node = queue.popleft()
    result.append(curr_node.val)
    
    if curr_node.left:
      queue.append(curr_node.left)
    if curr_node.right:
      queue.append(curr_node.right)

  return result

breadth-first search

0 / 15

Summary

BFS is a traversal algorithm that visits all nodes at a particular level before moving to the next level.
BFS uses a queue to keep track of the nodes it needs to visit.

Processing Levels

The distinguishing feature of BFS is that it visits all nodes at a particular level before moving onto the nodes at the next level.

DESCRIPTION

Given a binary tree, return the level-order traversal of its nodes' values. (i.e., from left to right, level by level).

Input

Output [[4], [2, 7], [1, 3, 6, 9]]

We can extend our basic BFS algorithm to calculate the number of nodes at each level by adding a for-loop that iterates over the size of the queue at the beginning of each level.

Each time the for-loop runs, we add the current node to the current_level list.
When the for-loop finishes, we have finished processing all nodes at that level, and we can add the current_level list to the result list. We can reset the current_level list to an empty list to prepare for the next level.

from collections import deque
    
def level_order(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        # number of nodes at the current level
        level_size = len(queue)
        current_level = []
        
        for _ in range(level_size):
            curr = queue.popleft()
            current_level.append(curr.val)
            
            if curr.left:
                queue.append(curr.left)
            if curr.right:
                queue.append(curr.right)
        
        # IMPORTANT
        # we have finished processing all nodes at the current level
        result.append(current_level)
        
    return result

To help you visualize how this algorithm works, the diagram below shows the state of the queue after we have finished processing the 2nd level of the tree.

Notice that queue contains the nodes at the 3rd level of the tree, [1, 3, 6, 9]. When we enter the next iteration of the while loop, the for loop will run 4 times to process these nodes.


from collections import deque
    
def level_order(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        # number of nodes at current level
        level_size = len(queue)
        current_level = []
        
        for _ in range(level_size):
            curr = queue.popleft()
            current_level.append(curr.val)
            
            if curr.left:
                queue.append(curr.left)
            if curr.right:
                queue.append(curr.right)
        
        # IMPORTANT
        # we have finished processing all
        # nodes at the current level
        result.append(current_level)
        
    return result

The state of the aglorithm after we have finished processing the nodes at the 2nd level of the tree.

Complexity Analysis

The base complexity of BFS is:

Next: Level Order Sum

Your account is free and you can post anonymously if you choose.

Loading comments...

BlogBehavioral Interview Examples Interviewing for Experienced SWEs All Blog Posts

Compare UsCompare to Interviewing.io

LinksFAQ Schedule Mock Interviews Pricing Become a Coach Our Coaches Learn System Design Learn DSA

LegalTerms and Conditions Privacy Policy

Contactsupport@hellointerview.com7511 Greenwood Ave North
Unit #4238 Seattle, WA 98103