Maximum Depth of Binary Tree - Python Solution

1. Introduction

The "Maximum Depth of Binary Tree" problem is a fundamental question in tree algorithms, focusing on calculating the depth or height of a binary tree. This problem is crucial for understanding recursive tree traversal and is often used to gauge one's grasp of tree data structures in coding interviews.

Problem

Given the root of a binary tree, the task is to return its maximum depth. The maximum depth of a binary tree is defined as the number of nodes along the longest path from the root node down to the farthest leaf node.

2. Solution Steps

1. Implement a recursive function to calculate the depth of the tree.

2. The depth of a node is 1 plus the maximum depth of its left and right subtrees.

3. Handle the base case where the node is null (a leaf's child).

4. Recursively calculate the depth for each node and return the maximum depth found.

3. Code Program

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

def maxDepth(root):
    if not root:
        return 0
    # Depth of a node is 1 plus the maximum depth of its left and right subtrees
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

# Example Usage
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20, TreeNode(15), TreeNode(7))
print(maxDepth(root))

Output:

3

Explanation:

1. Recursive Function: maxDepth calculates the depth of a tree recursively. It checks each node and calculates the depth.

2. Depth Calculation: The depth of a node is computed as 1 (for the node itself) plus the maximum depth of its left and right subtrees.

3. Base Case: When a node is null, which happens for a leaf's children, the depth is considered 0.

4. Recursion: The function recursively calculates the depth for each node and returns the maximum depth found in the binary tree.