To solve the “Maximum Depth of Binary Tree” problem, we can use a recursive approach to traverse the binary tree and calculate the maximum depth. The depth of a node is defined as the length of the path from the root to that node.

Here’s the implementation:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_depth(root: TreeNode) -> int:
    if not root:
        return 0

    # Calculate the depth of the left and right subtrees
    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)

    # The maximum depth is the maximum of the depths of left and right subtrees, plus 1 for the current node
    return max(left_depth, right_depth) + 1

# Example usage:
root = TreeNode(4, 
                TreeNode(8), 
                TreeNode(10, 
                         TreeNode(12), 
                         TreeNode(7)))

result = max_depth(root)  # Maximum depth of the tree: 3
print(result)
assert result == 3

Explanation:

  • The max_depth function calculates the maximum depth of a binary tree using recursion.
  • If the current node is None, the depth is 0.
  • Otherwise, it calculates the depths of the left and right subtrees recursively.
  • The maximum depth is the maximum of the depths of left and right subtrees, plus 1 for the current node.

Time Complexity:

The time complexity is O(N), where N is the number of nodes in the binary tree. In the worst case, we need to visit every node once.

Space Complexity:

The space complexity is O(H), where H is the height of the binary tree. This is the maximum depth of the recursive call stack. In the worst case, the depth of the recursion is equal to the height of the tree.