maximum_depth_of_binary_tree.py

from collections import deque
from typing import Optional


class TreeNode:
    """LeetCode provides this class; repeated here so the file runs standalone."""

    def __init__(self, val: int = 0, left: "Optional[TreeNode]" = None,
                 right: "Optional[TreeNode]" = None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """LeetCode #104 - Maximum Depth of Binary Tree (Easy)
    https://leetcode.com/problems/maximum-depth-of-binary-tree/

    Return the number of nodes along the longest path from the root down to a
    leaf. An empty tree has depth 0.
    """

    def maxDepth(self, root: Optional[TreeNode]) -> int:
        """Recursive DFS - the depth of a tree is 1 + the deeper subtree.

        Key insight: the definition is already recursive, so the code is just
        the definition written down. The empty tree is the base case that stops
        the recursion, and it is also the correct answer for it (0).

        Time:  O(n) - each node contributes one call.
        Space: O(h) - recursion depth; O(log n) if balanced, O(n) if a chain.
        """
        if root is None:
            return 0

        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

    def max_depth_bfs(self, root: Optional[TreeNode]) -> int:
        """Iterative BFS - count the levels while walking them one at a time.

        The trick that makes level-by-level BFS work: snapshot len(queue) before
        the inner loop. That is exactly how many nodes belong to the current
        level, so the children appended during the loop are not mixed into it.

        Time:  O(n)
        Space: O(n) - the widest level of the tree.
        """
        if root is None:
            return 0

        queue = deque([root])
        levels = 0

        while queue:
            for _ in range(len(queue)):     # exactly one full level
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            levels += 1

        return levels