How do you solve Maximum Depth of Binary Tree on LeetCode?

Maximum Depth of Binary Tree (LeetCode #104) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(h) space complexity. Key insight: The maximum depth is determined by the longest path from the root to any leaf.

What is the brute force solution for Maximum Depth of Binary Tree?

The brute force approach for Maximum Depth of Binary Tree is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves calculating the depth of each leaf node by traversing the tree. We can do this by recursively checking each node and counting the levels until we reach the leaves. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Maximum Depth of Binary Tree?

Clarify the definition of maximum depth with the interviewer. Consider edge cases, such as an empty tree. Explain your thought process while coding to showcase your understanding.

What are common mistakes when solving Maximum Depth of Binary Tree?

Forgetting to handle the null case, which can lead to null pointer exceptions. Not understanding the difference between depth and height.

#104

Maximum Depth of Binary Tree

Easy

TreeDepth-First SearchBreadth-First SearchBinary TreeDepth-First SearchRecursion

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(h)

💡

Intuition

Time O(n)Space O(h)

The optimal approach uses a single traversal of the tree to calculate the maximum depth. We can do this using Depth-First Search (DFS) or Breadth-First Search (BFS) to efficiently find the depth in linear time.

⚙️

Algorithm

4 steps

1Step 1: If the current node is null, return 0 (base case).
2Step 2: Recursively calculate the depth of the left subtree.
3Step 3: Recursively calculate the depth of the right subtree.
4Step 4: Return the maximum of the two depths plus one (for the current node).

solution.py6 lines

1def maxDepth(root):
2    if not root:
3        return 0
4    left_depth = maxDepth(root.left)
5    right_depth = maxDepth(root.right)
6    return 1 + max(left_depth, right_depth)

ℹ

Complexity note: This complexity is linear because we visit each node exactly once. The space complexity is O(h) due to the recursion stack, where h is the height of the tree.

1The maximum depth is determined by the longest path from the root to any leaf.
2Recursive approaches are often easier to implement for tree problems.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.