0104_maximum_depth_of_binary_tree.py

"""104. Maximum Depth of Binary Tree  —  Easy

LeetCode: https://leetcode.com/problems/maximum-depth-of-binary-tree/

Problem
-------
Given the root of a binary tree, return the length of its longest root-to-leaf
path measured in number of nodes (not edges).  A leaf is a node with no
children.  The depth of an empty tree is 0.

Examples
--------
    Input:  root = [3, 9, 20, null, null, 15, 7]
    Output: 3
    Explanation: The path 3 → 20 → 7 (or 3 → 20 → 15) has 3 nodes.

    Input:  root = [1, null, 2]
    Output: 2

Intuition
---------
The depth of a node equals 1 plus the maximum depth of its two subtrees.
Ask each subtree for its depth, take the larger, add one — that is the full
recursion in one sentence.

Approach
--------
1. Base case: an empty node (None) has depth 0.
2. Recursive case: recurse left and right, return 1 + max(left_depth,
   right_depth).

Each recursive call returns "the deepest I can reach from here", so the root
call returns the answer directly — this is the classic "return value" DFS
framing.

Brute force would be identical; there is no inefficiency to remove.  BFS
level-order traversal is an alternative: push nodes level by level and count
levels until the queue empties.  Recursive DFS is simpler code.

Complexity
----------
Time:  O(n)   every node is visited exactly once.
Space: O(h)   the call stack depth equals the tree height h; O(log n) for a
              balanced tree, O(n) worst-case for a skewed tree.

Edge cases
----------
- Empty tree (root is None) → return 0.
- Single node → return 1.
- Completely skewed tree (linked-list shape) → depth equals n.

Pattern: DFS Recursion (post-order), BFS level-order (alternative).
ML relevance: Decision-tree max depth is a direct hyperparameter; this
              function computes exactly that value for any tree.
"""
from __future__ import annotations

from collections import deque
from typing import Optional


class TreeNode:
    """Standard LeetCode binary-tree node."""

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


class Solution:
    """LeetCode submission class."""

    def maxDepth(self, root: Optional[TreeNode]) -> int:  # noqa: N802
        """Return the maximum depth using post-order DFS recursion."""
        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:
        """Return the maximum depth using BFS level-order traversal.

        Alternative approach: count levels as we sweep the tree breadth-first.
        Same O(n) time but O(w) space where w is the maximum level width.
        """
        if root is None:
            return 0
        depth = 0
        queue: deque[TreeNode] = deque([root])
        while queue:
            depth += 1
            for _ in range(len(queue)):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return depth


# ---------------------------------------------------------------------------
# Helpers
# ---------------------------------------------------------------------------

def _build_tree(values: list[int | None]) -> Optional[TreeNode]:
    """Build a binary tree from a LeetCode-style level-order list."""
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue: deque[TreeNode] = deque([root])
    index = 1
    while queue and index < len(values):
        node = queue.popleft()
        if index < len(values) and values[index] is not None:
            node.left = TreeNode(values[index])  # type: ignore[arg-type]
            queue.append(node.left)
        index += 1
        if index < len(values) and values[index] is not None:
            node.right = TreeNode(values[index])  # type: ignore[arg-type]
            queue.append(node.right)
        index += 1
    return root


def _demo() -> None:
    """Run worked examples as assertions."""
    solver = Solution()

    # [3, 9, 20, null, null, 15, 7] → depth 3
    root1 = _build_tree([3, 9, 20, None, None, 15, 7])
    assert solver.maxDepth(root1) == 3
    assert solver.max_depth_bfs(root1) == 3

    # [1, null, 2] → depth 2
    root2 = _build_tree([1, None, 2])
    assert solver.maxDepth(root2) == 2
    assert solver.max_depth_bfs(root2) == 2

    # Empty tree → 0
    assert solver.maxDepth(None) == 0
    assert solver.max_depth_bfs(None) == 0

    # Single node → 1
    root3 = _build_tree([42])
    assert solver.maxDepth(root3) == 1

    print("All tests passed.")


if __name__ == "__main__":
    _demo()