104. Maximum Depth of Binary Tree

[#binary-tree, #dfs]

## description

## 104. Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

plain text

Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:

plain text

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

–
The number of nodes in the tree is in the range [0, 104].
–
-100 <= Node.val <= 100

Constraints:

## notes

### Intuition

The maximum depth of a binary tree is the longest path from root to any leaf. At each node, the depth is one plus the maximum depth of its subtrees.

### Implementation

Create a recursive DFS function that takes the current node and accumulated depth. When the node is None, we've gone past a leaf, so return the current depth. Otherwise, recurse on both children with depth + 1 and return the maximum of the two results.

### Edge-cases

An empty tree (null root) returns 0, which the base case handles naturally.

–
Time: O(n) — visit every node
–
Space: O(n) — worst case recursion depth for a skewed tree; O(log n) for balanced

### Complexity

## solution

python

from typing import Optional
from lcutils import TreeNode

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def dfs(self, root: Optional[TreeNode], depth: int) -> int:
        if not root:
            return depth
        return max(self.dfs(root.left, depth + 1), self.dfs(root.right, depth + 1))
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        return self.dfs(root, 0)
        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()

--EOF--