Breadth First Search (BFS)

Author: @heiheihang

Overview

In Breadth-First Search (BFS), we explore all the closest nodes first before going one step further. A good example would be:

Given a binary tree, find the closest node from root that has the value 3

Of course, you may use DFS to find the solution by iterating all nodes. However, as you can imagine, if the target node is the right child of the root, we have wasted so much time iterating the entire left branch of the root!

BFS would immediately locate the closest target node without wasting time iterating deeper nodes.

We will introduce the following template for BFS:

def findTargetNode(root, targetValue):
    if(root is None):
        return None
    
    #currentLevel contains the nodes with the same distance to root (closest so far)
    currentLevel = [root]
    
    #we increase our depth one by one as long as there is still node
    while(len(level) > 0):
    
        #we store the current level node's children in nextLevel
        nextLevel = []
        
        for node in currentLevel:
            #skip if the node is None
            if(node is None):
                continue
            #we can be sure the target node is the CLOSEST so we can return
            #because we are traversing the tree level by level
            if(node.val == targetValue):
                return node
                
            #add the children to nextLevel
            nextLevel.append(node.left)
            nextLevel.append(node.right)
        #change the currentLevel to nextLevel (no target node in this level, go next)
        currentLevel = nextLevel
    
    #if no target node has been returned    
    return None
    
    

In general, we use a queue to model BFS. As the head of the queue represents the closest nodes, and the tail of the queue represents the furthest nodes. We look at the head of the queue, and add new nodes to the end of the queue.

We can start applying this template to the following problem (LeetCode Link).

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted.

In this problem, our primary goal is to separate the tree into different levels. For example, we have these following levels:

1. [1]
2. [2,3]
3. [4, _, 3, 5]

When we can separate the tree into different levels, we are just one step before obtaining the solution (which is just getting the averages of each list)

The challenge here is how can we separate the tree into different levels. We can use the template above with currentLevel and nextLevel.

def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        answer = []

        #saves the nodes in the currentLevel
        currentLevel = [root]

        #continue traversing as long as there is still unexplored nodes
        while(len(currentLevel) > 0):

            #stores the children of the nodes in the currentLevel
            nextLevel = []

            #stores the total sum of the currentLevel nodes
            currentLevelNodeCount = 0
            
            currentLevelSum = 0
            for node in currentLevel:
                if(node is None):
                    continue
                currentLevelSum += node.val
                nextLevel.append(node.left)
                nextLevel.append(node.right)
                currentLevelNodeCount += 1
            #calculate the level average
            if currentLevelNodeCount:
                currentLevelAverage = currentLevelSum / currentLevelNodeCount
                
                answer.append(currentLevelAverage)

            #explore the nextLevel
            currentLevel = nextLevel
        return answer

We should keep practising the this template of BFS in these similar problems.

Suggested Problems

Problem Name	Difficulty	Solution Link
0101 - Symmetric Tree	Easy	View Solutions
0199 - Binary Tree Right Side View	Medium	View Solutions
0103 - Binary Tree Zigzag Level Order Traversal	Medium	View Solutions