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?
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.