104. Maximum Depth of Binary Tree

Problem Link

The depth of a binary tree is defined as the length of the longest path from the root to any leaf. This naturally suggests a recursive, bottom-up way of thinking.

For any given node, if we already know the maximum depth of its left and right subtrees, then the depth of this node is simply one (for the current node) plus the larger of those two depths. This breaks the problem into identical subproblems on smaller trees.

The base case occurs when we reach a None node, which contributes a depth of 0. As the recursion unwinds, each node computes its depth using the results from its children, and the maximum value propagates back up to the root.

---

Pseudocode

    if node is null:
    return 0
    leftDepth = maxDepth(node.left)
    rightDepth = maxDepth(node.right)
    return 1 + max(leftDepth, rightDepth)

Runtime Complexity

Time: \(O(n)\)

Space: \(O(h)\)

PythonGo

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

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

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return 1 + max(maxDepth(root.Left), maxDepth(root.Right))
}

---