Solutions

# +1 at every recursion. Recursive or iterative (stack) DFS, or BFS (deque)
# trees

# Recursive DFS - O(n) time, O(h) space
def max_depth(root: TreeNode) -> int:
    if not root:
        return 0
    
    return max(max_depth(root.left), max_depth(root.right)) + 1


# Iterative DFS - O(n) time, O(n) space
def max_depth(root: TreeNode) -> int:
    stack = [[root, 1]]
    res = 0

    while stack:
        node, depth = stack.pop()

        if node:
            res = max(res, depth)

            stack.append([node.left, depth + 1])
            stack.append([node.right, depth + 1])
    return res


# BFS - O(n) time, O(n) space
from collections import deque

def max_depth(root: TreeNode) -> int:
    q = deque([root])
    if root:
        q.append(root)

    level = 0
    while q:
        for _ in range(len(q)):
            node = q.popleft()
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        level += 1
    return level