Maximum Depth of Binary Tree Problem on LeetCode in Python

Spread the love

Introduction

Binary trees are an essential data structure in computer science, widely used in various algorithms and real-world applications. The Maximum Depth of Binary Tree problem on LeetCode requires us to find the depth or height of a given binary tree. In this article, we will explore different approaches to solve this problem using Python and understand their advantages and disadvantages.

Table of Contents

  1. Introduction
  2. Understanding the Problem Statement
  3. Recursive Approach
  4. Iterative Approach Using Depth-First Search
  5. Iterative Approach Using Breadth-First Search
  6. Time and Space Complexity Analysis
  7. Practical Applications
  8. Conclusion

Understanding the Problem Statement

The Maximum Depth of Binary Tree problem is defined as follows:

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: root = [3,9,20,null,null,15,7]
Output: 3

In simpler terms, we need to find the length of the longest path from the root to any leaf in the binary tree.

Recursive Approach

One of the most intuitive approaches to solve this problem is using recursion. We can recursively calculate the height of the left and right subtrees of a node and use these heights to calculate the node’s height. The height of a node is the maximum of the heights of its left and right children, plus one.

Here’s what the Python code looks like:

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

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        left_height = self.maxDepth(root.left)
        right_height = self.maxDepth(root.right)
        
        return max(left_height, right_height) + 1

Iterative Approach Using Depth-First Search

An alternative to the recursive approach is to use an iterative depth-first search. We can use a stack to keep track of the nodes and their depths. For each node, we update the maximum depth encountered so far.

Here’s the Python code for this approach:

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        max_depth = 0
        stack = [(root, 1)]
        
        while stack:
            node, depth = stack.pop()
            max_depth = max(max_depth, depth)
            if node.left:
                stack.append((node.left, depth + 1))
            if node.right:
                stack.append((node.right, depth + 1))
        
        return max_depth

Iterative Approach Using Breadth-First Search

Another iterative approach is using a breadth-first search. We can use a queue to keep track of the nodes at each level. For each level, we process all the nodes in that level, and then move on to the next level until the queue is empty.

Here’s the Python code for this approach:

from collections import deque

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        depth = 0
        queue = deque([(root)])
        
        while queue:
            level_length = len(queue)
            for i in range(level_length):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            depth += 1
        
        return depth

Time and Space Complexity Analysis

  1. Recursive Approach: The time complexity is O(n), where n is the number of nodes in the tree, as each node is visited once. The space complexity is O(h), where h is the height of the tree, accounting for the recursive call stack.
  2. Iterative Approach Using Depth-First Search: The time complexity is also O(n), as each node is pushed and popped from the stack once. The space complexity is O(h), accounting for the stack storage.
  3. Iterative Approach Using Breadth-First Search: The time complexity is O(n), as each node is enqueued and dequeued once. The space complexity is O(w), where w is the maximum width of the tree, accounting for the queue storage.

Conclusion

In this article, we explored the Maximum Depth of Binary Tree problem on LeetCode and discussed three different approaches in Python: a recursive approach, an iterative approach with depth-first search, and an iterative approach with breadth-first search. Each approach has its own advantages, and the choice depends on the specific use case and constraints.

Leave a Reply