104. Maximum Depth of Binary Tree

Approach: DFS

Use depth-first search to traverse the tree and calculate the maximum depth.

Algorithm:

1. If the root is None, return 0.
2. Recursively calculate the maximum depth of the left and right subtrees.
3. Return the maximum of the two depths plus 1.

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

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

        return max(left_depth, right_depth) + 1

• Time: $O(n)$ — where $n$ is the number of nodes in the tree, as we visit each node exactly once.
• Space: $O(h)$ — where $h$ is the height of the tree, due to the recursive call stack.

Last updated on