pythonalgorithmbinary-treebreadth-first-search

maximum depth of a binary tree using BFS- why is the depth doubled what it is supposed to be?


I am writing iterative solution to finding the max depth of a binary tree- using Breadth First Search (BFS):

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

from collections import deque
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: 
            return 0

        queue = deque()
        queue.append(root)
        depth = 1
        level_length = len(queue)

        while queue: 
            for i in range(level_length): 
                node = queue.popleft() 

                if node.left: 
                    queue.append(node.left)

                if node.right: 
                    queue.append(node.right)
                    
            depth +=1 
            
        return depth

For the input root = [3,9,20,null,null,15,7], I am getting output=6 rather than 3, which is clearly the correct answer.

I've gone through my code several times on paper, but can't seem to see where it is falling short- any ideas?


Solution

  • level_length = len(queue) is only computed one time before the traversal begins, so it's always 1. This means your inner for loop never runs more than once and is effectively nonexistent, causing depth += 1 to run on every node.

    Move the length computation into the while so that the for loop runs the correct number of times for each level before incrementing depth.

    Leetcode wants depth = 0 instead of depth = 1, but you'd probably figure this out after fixing the main bug.