Maximum Depth of a Binary Tree : Leetcode Solution.

Introduction

The depth of a binary tree is one of the fundamental properties used to understand its structure. Calculating the maximum depth of a binary tree involves determining the longest path from the root node to a leaf node. This article explains a recursive solution to solve the Maximum Depth of Binary Tree problem.

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

Input:

    3
   / \
  9  20
     /  \
    15   7

Output:

3

Explanation:

• The longest path is: 3 -> 20 -> 15 or 3 -> 20 -> 7, which includes 3 nodes.

Approach

The solution leverages recursion to compute the depth of each subtree, starting from the root. The depth of a node is calculated as:

[ \text{Depth} = 1 + \max(\text{Depth of left subtree}, \text{Depth of right subtree}) ]

Steps:

1. Base Case:

   • If the current node is None, return 0 (a null tree has depth 0).

2. Recursive Case:

   • Compute the depth of the left subtree using self.maxDepth(root.left).

   • Compute the depth of the right subtree using self.maxDepth(root.right).

   • Take the maximum of the two depths and add 1 (to account for the current node).

3. Return Result:

   • Return the calculated depth.

Complexity

• Time Complexity: $$O(n)$$

  • Each node is visited exactly once, where $$n$$ is the total number of nodes in the tree.

• Space Complexity: $$O(h)$$

  • The recursion stack depth depends on the height of the tree, where $$h$$ is the height of the tree.

Python Code

Here is the Python implementation of the solution:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution(object):
    def maxDepth(self, root):
        if not root:
            return 0

        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

Example Walk-through

Let’s walk through the algorithm with the input tree:

Input Tree:

    3
   / \
  9  20
     /  \
    15   7

Steps:

1. Start at the root node (3).

2. Recursively calculate the depth of the left subtree:

   • root.left is 9 → Both children are None, so depth is 1.

3. Recursively calculate the depth of the right subtree:

   • root.right is 20 →

     • Left child is 15 (depth 1).

     • Right child is 7 (depth 1).

     • Depth of 20 is 1 + max(1, 1) = 2.

4. Depth of 3 is 1 + max(1, 2) = 3.

Output:

3

Advantages of Recursion in Tree Depth Calculation

1. Simplicity: Recursive solutions are concise and closely mirror the definition of a binary tree.

2. Efficiency: Each node is processed once, ensuring optimal performance.

Conclusion

This recursive solution efficiently computes the maximum depth of a binary tree. Understanding this algorithm provides a foundation for solving more advanced tree problems, such as finding the diameter or balancing a binary tree.

If you found this article helpful, feel free to explore more tree-related problems and techniques!

Let’s Connect! If you enjoyed this article, feel free to connect with me on LinkedIn and check out more of my articles on Hashnode!