Maximum Depth of Binary Tree

The problem description can be found in LeetCode.

Approach

This is a classic Tree problem and such pattern is very important to understand for solving other problems.

Here, we simply calculate the left and right depth and return the maximum between them. The same is applied to all the node, recursively.

Solution

from typing import Optional


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

        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)

        return 1 + max(left_depth, right_depth)

Complexity

• Time: $O(n)$
• Space: $O(h)$

Where $n$ is the number of nodes in the tree and $h$ is its height. If the tree is unbalanced, it is like having a Linked List, hence $h=n$.