Tree BFS

Question 1

What is the pattern and when is Tree BFS used?

Answer 1

Tree BFS explores tree level by level using a queue.

Use Case: Level-order traversal, shortest path in trees.

Example: [Minimum Depth of Binary Tree]. Action: Verbalize use case aloud.

Question 2

What are the key steps in Tree BFS?

Answer 2

1. Initialize queue with root.
2. Process node, enqueue children.
3. Repeat until queue empty.

Action: Explain steps for [Minimum Depth of Binary Tree] aloud.

Question 3

How does Tree BFS apply to [Minimum Depth of Binary Tree]?

Answer 3

The problem is to find minimum depth to leaf. The approach is to use queue for level-order, returning depth of first leaf.

Action: Verbalize solution logic aloud.

Question 4

What are the complexity and gotchas of Tree BFS?

Answer 4

Time complexity is O(n), space complexity is O(w), where w is the width.

Gotchas: Empty tree, skewed tree.

Action: List edge cases for [Minimum Depth of Binary Tree] aloud.

Question 5

Code example of Tree BFS.

Answer 5

```python
from typing import Optional
class TreeNode:
def __init__(self, val: int = 0, left: ‘TreeNode’ = None, right: ‘TreeNode’ = None) -> None:
self.val = val
self.left = left
self.right = right
from collections import deque
def min_depth(root: Optional[TreeNode]) -> int:
if not root:
return 0
queue = deque([(root, 1)])
while queue:
node, depth = queue.popleft()
if not node.left and not node.right:
return depth
if node.left:
queue.append((node.left, depth + 1))
if node.right:
queue.append((node.right, depth + 1))
return 0
~~~