LeetCode 104 - Maximum Depth of Binary Tree

This Easy problem asks for the maximum depth of a binary tree. I used DFS to reach the end of both subtrees and returned the larger depth from the two recursive branches.

---

Problem link and explanation

• Problem: 104. Maximum Depth of Binary Tree
• Summary: Given the root of a binary tree, return the number of nodes on the longest path from the root to a leaf.

An empty tree has depth zero, while a tree containing only the root has depth one. At every node, the deeper of the left and right subtrees determines the maximum depth below that point.

---

Approach

The recursive function receives the current node and the depth reached so far. When the node is None, there is no further node to count, so it returns the current depth.

if not node:
    return depth

For a real node, both recursive calls advance the depth by one. The larger result is the deepest leaf reachable through that node.

left = self.dfs(node.left, depth + 1)
right = self.dfs(node.right, depth + 1)
return max(left, right)

Starting the root at depth zero means that moving through the root increments the value to one. A None child below a leaf then returns a depth that includes that leaf.

---

Troubleshooting

The initialization depends on whether depth counts nodes or edges. This problem counts nodes from the root through the leaf, so the root call starts at zero and the value increases when recursion moves past an actual node.

Under this convention, an empty root immediately returns zero. A single root sends depth one to both None children, and the maximum is one. Checking both cases catches the usual off-by-one error.

---

Complexity analysis

• Time complexity: O(n)
  • Every node is visited once to determine the deepest path.
• Space complexity: O(h)
  • The recursion stack grows with the tree height. It is O(log n) for a balanced tree and O(n) for a skewed tree.

---

Implementation code

from typing import Optional

class Solution:
    def dfs(self, node: Optional[TreeNode], depth: int) -> int:
        if not node:
            return depth

        left = self.dfs(node.left, depth + 1)
        right = self.dfs(node.right, depth + 1)
        return max(left, right)

    def maxDepth(self, root: Optional[TreeNode]) -> int:
        return self.dfs(root, 0)

---

Summary and reflection

The maximum depth follows directly from taking the larger result of the left and right recursive calls. The implementation detail that needs a fixed convention is how depth is counted. Starting at zero and incrementing when passing an actual node handles empty and single-node trees with the same recursion.