Problem Statement

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:

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

Example 2:

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

Key Insights

We can

Recursive Solution

# 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

from collections import deque
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        """
            Time:
                * O(N) ~ each node visited once
            Space:
                * O(N) ~ worst case (one branch)
                * O(log N) ~ completely balanced
        """
        if not root:
            return 0
        else:
            # For each node, find the height of the
            # left and right subtrees
            left  = self.maxDepth(root.left)
            right = self.maxDepth(root.right)
            # By adding 1 at each level along the
            # longest path, we can find the height
            # of the binary tree.
            return max(left, right) + 1

Iterative Solution

# 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

from collections import deque
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        """
            Time:
                * O(N) ~ each node visited once
            Space:
                * O(N) ~ worst case (one branch)
                * O(log N) ~ completely balanced
        """
        if not root:
            return 0
        # Add the root to the queue.
        queue = deque([(root, 0)])
        ans = 0

        while queue:
            # At each node, increment the height
            # and update the global max height
            node, height = queue.popleft()
            height += 1
            ans = max(ans, height)
            # Add the left and right node to the 
            # queue.
            if node.left:
                queue.append((node.left, height))

            if node.right:
                queue.append((node.right, height))

        return ans

Leetcode 104 Maximum Depth of Binary Tree