1 month, 1 week

Coding Patterns: Breadth First Search




Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory, usually a queue, is needed to keep track of the child nodes that were encountered but not yet explored.

This pattern is very useful to solve the problems involving traversal of a tree in a level-by-level order

Problem: Binary Tree Level Order Traversal

LeetCode 102 - Binary Tree Level Order Traversal [medium]

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

We can use a Queue to efficiently traverse in BFS fashion. Here are the steps of our algorithm:

Start by pushing the root node to the queue.
Keep iterating until the queue is empty.
In each iteration, first, count the elements in the queue.

We will have these many nodes at the current level.
Next, remove level_size nodes from the queue and push their value into an array to represent the current level.
After removing each node from the queue, insert both of its children into the queue.
If the queue is not empty, repeat step 3 for the next level.

Solution:                                                                                                                                                          


class TreeNode:                                                                        
     def __init__(self, val=0, left=None, right=None):                  
         self.val = val                                                                     
         self.left = left                                                                    
         self.right = right                                                                  
class Solution:                                                                             
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:                                                                             
            return None                                                                     
        q = [root]                                                                             
        ret = []                                                                                 
        while q:                                                                              
            temp = []                                                                          
            for i in range(len(q)):                                                      
                node = q.pop(0)                                                           
                temp.append(node.val)                                               
                if node.left:                                                               
                    q.append(node.left)                                             
                if node.right:                                                            
                    q.append(node.right)                                         
            ret.append(temp)                                                      
        return ret                                                                      

Time ComplexityO(n) where n is the total number of nodes in the tree.

Space ComplexityO(n), since we need an O(n) space to return the result. We will also need O(n) for the queue.

When the problem asks for the traversal of a tree, you should think about BFS pattern and use it in combination with the Queue structure.

LeetCode 104 - Maximum Depth of Binary Tree [easy]

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

1.Solution:                                                                                      

class Solution:                                                                    
    def maxDepth(self, root: Optional[TreeNode]) -> int:      
        maxD = 0                                                                     
        queue = []                                                                    
        if root is not None:                                                     
            queue.append(root)                                          
        while len(queue) > 0:                                          
            for i in range(len(queue)):                                      
                node = queue.pop(0)                                        
                if node.left:                                                           
                    queue.append(node.left)                                
                if node.right:                                                    
                    queue.append(node.right)                            
            maxD += 1                                                             
        return maxD                                                              

2. Solution:                                                                                              

class Solution:                                                                                 
    def maxDepth(self, root: Optional[TreeNode]) -> int:                   
        if root is None:                                                                           
            return 0                                                                                          
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

LeetCode 107 - Binary Tree Level Order Traversal II [easy]

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

Solution:                                                                                              

class Solution:                                                                                          
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        q = collections.deque()                                                                   
        q.append(root)                                                                               
        res = []                                                                                          
        while q:                                                                                           
            level = []                                                                                    
            for _ in range(len(q)):                                                               
                node = q.popleft()                                                               
                if node:                                                                               
                    q.append(node.left)                                                          
                    q.append(node.right)                                                    
                    level.append(node.val)                                                
            if level:                                                                               
                res.append(level)                                                        
        return res[::-1]                                                                             

LeetCode 111 - Minimum Depth of Binary Tree [easy]                         

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Solution:                                                                               

class Solution:                                                                            
    def minDepth(self, root: Optional[TreeNode]) -> int:             
        if not root:                                                                          
            return 0                                                                        
        queue = deque()                                                               
        queue.append([root, 1])                                                   
        while queue:                                                                    
            for i in range(len(queue)):                                              
                curr, depth = queue.popleft()                                  
                if not curr.left and not curr.right:                           
                    return depth                                                  
                if curr.left:                                                             
                    queue.append([curr.left, depth+1])                 
                if curr.right:                                                       
                    queue.append([curr.right, depth+1])             
        return 0                                                                     

LeetCode  637- Average of Levels in Binary Tree                                     

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.

Solution:                                                                                   

class Solution:                                                                                    
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        res = []                                                                                         
        queue = [root]                                                                               
        while queue:                                                                                 
            temp = []                                                                                  
            sumVal = 0                                                                              
            for node in queue:                                                                       
                sumVal += node.val                                                             
                if node.left:                                                                         
                    temp.append(node.left)                                                   
                if node.right:                                                                      
                    temp.append(node.right)                                               
            res.append(sumVal / len(queue))                                          
            queue = temp                                                                         
        return res                                                                                       


Responses(0)







Related