#104

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Maximum Depth of Binary Tree

Find the maximum depth of a binary tree using traversal techniques to track the longest path from root to leaf.

tree depth first search breadth first search binary tree

Problem Statement

Given a binary tree, your task is to determine its maximum depth. The depth is defined as the number of nodes along the longest path from the root node to the farthest leaf node. The problem asks for this value to be returned as an integer.

For example, given the binary tree root = [3,9,20,null,null,15,7], the maximum depth is 3. The solution requires either Depth-First Search (DFS) or Breadth-First Search (BFS), both of which can be implemented recursively or iteratively.

Examples

Example 1

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

Output: 3

Example details omitted.

Example 2

Input: root = [1,null,2]

Output: 2

Example details omitted.

Constraints

The number of nodes in the tree is in the range [0, 104].
-100 <= Node.val <= 100

Solution Approach

Depth-First Search (DFS) Recursive Approach

In this approach, you recursively explore the left and right subtrees for each node. The depth of the tree is computed as the maximum of the depths of the left and right subtrees, plus one for the current node. This method can be implemented using simple recursion and provides a clear, concise solution.

Breadth-First Search (BFS) Iterative Approach

BFS can be used iteratively to compute the tree depth. Starting from the root, you explore each level of the tree one by one. Each level’s nodes are processed, and the depth is incremented with every level processed. This approach ensures the maximum depth is found once all nodes have been visited.

State Tracking for Optimal Solution

To optimize the solution, tracking the depth while traversing the tree is essential. Both DFS and BFS can be enhanced by maintaining a running maximum depth, ensuring you only calculate the final result after all levels are explored. This method is efficient and minimizes redundant calculations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution is O(n), where n is the number of nodes in the binary tree. This is because every node must be visited. The space complexity depends on the traversal method: DFS has O(h) space complexity (where h is the height of the tree) due to the recursion stack, while BFS has O(w) space complexity (where w is the width of the tree).

What Interviewers Usually Probe

Do you understand how to traverse a tree using both DFS and BFS approaches?
Can you describe how state tracking in traversal ensures the correct calculation of the tree's maximum depth?
Will you be able to explain the time and space complexity trade-offs between DFS and BFS for this problem?

Common Pitfalls or Variants

Common pitfalls

Failing to handle edge cases, such as an empty tree (null root).
Confusing tree depth with the number of nodes or height of the tree.
Not considering the impact of recursion depth in DFS when working with large trees.

Follow-up variants

Find the minimum depth of a binary tree (minimum number of nodes along a path).
Determine if a binary tree is balanced (the depths of the two subtrees of every node differ by no more than 1).
Implement a solution to find the diameter of a binary tree (the longest path between any two nodes).

FAQ

What is the maximum depth of a binary tree?

The maximum depth of a binary tree is the number of nodes along the longest path from the root node to a leaf node.

How do you calculate the maximum depth using DFS?

In DFS, you recursively traverse both the left and right subtrees, comparing the depths, and return the maximum depth encountered plus one for the current node.

Can you solve Maximum Depth of Binary Tree using BFS?

Yes, BFS iteratively explores each level of the tree, incrementing the depth with each level processed, ensuring the maximum depth is found after visiting all nodes.

What are the common pitfalls when solving Maximum Depth of Binary Tree?

Common pitfalls include failing to handle empty trees, confusing depth with the number of nodes, and not managing recursion depth in DFS for large trees.

How does state tracking help in the maximum depth problem?

State tracking ensures that you keep track of the current depth as you traverse the tree, allowing for an efficient and accurate calculation of the maximum depth.

terminal

Solution

Solution 1: Recursion

Recursively traverse the left and right subtrees, calculate the maximum depth of the left and right subtrees, and then take the maximum value plus $1$.

1

2

3

4

5

6

7

8

9

10

11

12

# Definition for a binary tree node.
# 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 root is None:
            return 0
        l, r = self.maxDepth(root.left), self.maxDepth(root.right)
        return 1 + max(l, r)

Continue Practicing

#101 symmetric tree #100 same tree #111 minimum depth of binary tree