Maximum Depth Of Binary Tree Leetcode Problem 104 [Python Solution]

In this blog post, we will explore the Maximum Depth Of Binary Tree LeetCode problem and provide an efficient Python solution at the end.

This problem falls under the “Trees” category and is categorized as “Easy.” The problem can be found on the LeetCode website at this link.

Problem Overview

The problem statement is quite simple: given the root of a binary tree, you need 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.

Example 1:

Input:

root = [3,9,20,null,null,15,7]

Output:

Example 2:

Input:

root = [1,null,2]

Output:

Constraints:

The number of nodes in the tree is in the range [0, 10^4].
The values of the nodes are within the range of -100 to 100. Now that we have a clear understanding of the problem, let’s explore different approaches to solve it.

Understanding Constraints

Before we delve into the solutions, let’s understand the constraints given in the problem statement:

The number of nodes in the tree is between 0 and 10^4. This means that we can have empty trees with no nodes, but also relatively large trees.
The values of the nodes are within the range of -100 to 100. This constraint informs us that the values in the nodes won’t exceed this range, making it easy to work with integer values.

Now that we have a clear picture of the problem and its constraints, let’s move on to the solutions.

Recursive Depth-First Search (DFS) Solution

The most straightforward way to solve this problem is by using a recursive depth-first search (DFS).

We’ll implement a Python solution using this approach.

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

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

In this solution, we define a TreeNode class to represent the structure of a binary tree.

The maxDepth function takes the root of the tree as input and calculates the maximum depth recursively.

Here’s the breakdown of the recursive approach:

We start by checking if the root is None.

If it is, this means we’ve reached the end of a branch, and we return a depth of 0.

If the root is not None, we calculate the depth of the left and right subtrees recursively using the maxDepth function and then take the maximum of these depths.
We add 1 to the maximum depth of the subtrees because we are including the current node in the depth calculation.

This approach explores the entire tree and calculates the maximum depth efficiently.

The time complexity is O(n), where n is the number of nodes in the tree.

The space complexity is O(h), where h is the height of the tree.

In the worst case, when the tree is completely unbalanced, the space complexity becomes O(n).

Iterative Depth-First Search (DFS) Solution

Now, let’s explore an iterative depth-first search solution.

This approach emulates the recursive stack using an explicit stack data structure.

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

        stack = [(root, 1)]
        max_depth = 0

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

            if node:
                max_depth = max(max_depth, depth)
                stack.append((node.left, depth + 1))
                stack.append((node.right, depth + 1))

        return max_depth

In this solution, we use a stack to perform an iterative depth-first search.

The stack contains pairs of nodes and their corresponding depths.

We start by pushing the root node onto the stack with an initial depth of 1. Here’s how the iterative approach works:

We check if the root is None and return 0 if it is, just like in the recursive solution.
We initialize a variable max_depth to keep track of the maximum depth seen so far.
We enter a while loop that continues as long as the stack is not empty.

Inside the loop, we pop a node and its depth from the stack.

If the node is not None, we update max_depth with the maximum of the current depth and the previously recorded maximum depth.

We then push the left and right children of the node onto the stack with an incremented depth.

This process continues until the stack is empty, and we return the max_depth as the final result.

This iterative approach achieves the same result as the recursive one, with a time complexity of O(n) and a space complexity of O(h), where h is the height of the tree.

Breadth-First Search (BFS) Solution

Now, let’s explore a breadth-first search (BFS) solution.

This approach involves traversing the tree level by level and counting the levels.

View on GitHub ➹

from collections import deque

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) -&gt; int:
        if not root:
            return 0

        q = deque()
        q.append(root)
        level = 0

        while q:
            for i 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

In this solution, we use a queue (implemented with a deque) to perform a breadth-first search.

We start by adding the root node to the queue, and we also initialize a variable level to keep track of the current level.

Here’s how the breadth-first search approach works:

We check if the root is None and return 0 if it is.
We enter a while loop that continues as long as the queue is not empty.
Inside the loop, we use a for loop to process all the nodes at the current level.

We remove each node from the front of the queue, check if it has left and right children, and add them to the queue if they exist.

After processing all nodes at the current level, we increment the level variable to move to the next level.
The loop continues until we’ve processed all levels in the tree, and we return the level as the maximum depth.

This BFS approach also has

a time complexity of O(n) and a space complexity of O(m), where m is the maximum number of nodes at a single level in the tree.

Time and Space Complexity

Recursive DFS Solution:

Time Complexity: O(n) – We visit each node in the tree once, where n is the number of nodes in the tree.
Space Complexity: O(h) – In the worst case, when the tree is completely unbalanced, the space complexity becomes O(n) due to the call stack.

However, in a balanced tree, the space complexity is O(log n), where log n is the height of the tree.

Iterative DFS Solution:

Time Complexity: O(n) – We visit each node in the tree once, where n is the number of nodes in the tree.
Space Complexity: O(h) – In the worst case, when the tree is completely unbalanced, the space complexity becomes O(n) due to the stack.

However, in a balanced tree, the space complexity is O(log n), where log n is the height of the tree.

BFS Solution:

Time Complexity: O(n) – We visit each node in the tree once, where n is the number of nodes in the tree.
Space Complexity: O(m) – In the worst case, where the tree is a complete binary tree, the space complexity becomes O(2^(h-1)), where h is the height of the tree.

In a balanced tree, it’s closer to O(2^(h-1)) as well, but in a completely unbalanced tree, it can be O(n).

Reasoning Behind Our Approach

The three solutions presented in this blog post offer different ways to approach the Maximum Depth Of Binary Tree problem.

Each approach has its own advantages and trade-offs:

The recursive depth-first search solution is simple and intuitive, but it relies on the call stack, which can lead to a high space complexity in the case of unbalanced trees.
The iterative depth-first search solution maintains control over the stack, reducing the space complexity compared to the recursive solution.

It also demonstrates the iterative nature of depth-first search.

The breadth-first search solution focuses on level-order traversal and is helpful for visualizing the depth of the tree.

It also provides a way to deal with the space complexity more efficiently by processing levels.

The choice of which solution to use depends on your preference and the specific requirements of your application.

All three solutions provide an efficient way to find the maximum depth of a binary tree, and you can choose the one that best suits your needs.

Conclusion

In this blog post, we explored the LeetCode problem Maximum Depth Of Binary Tree and provided Python solutions using different approaches.

We covered recursive depth-first search, iterative depth-first search, and breadth-first search solutions.

Each approach has its own advantages and can be chosen based on the specific context and requirements of your application.

This problem is categorized as “Easy,” but it’s a fundamental concept in tree traversal and can help you build a strong foundation for more complex tree-related problems.

We encourage you to practice these solutions and explore additional tree-related challenges to strengthen your problem-solving skills.

Feel free to comment, ask questions, make suggestions, or share this content with others who might find it helpful.

Happy coding!

Problem Link