Tree: Depth-First Search - Maximum Depth of Binary Tree
Consider the following BFS-based Python code to compute the maximum depth of a binary tree. Given the tree below, what is the value of
depth after the second iteration of the while loop?
Tree structure:
- Root node 1
- Left child 2
- Right child 3
- Left child of 2 is 4
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxDepth(root):
if root is None:
return 0
queue = deque([root])
depth = 0
while queue:
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
depth += 1
return depth
root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))
print(maxDepth(root))