Maximum Depth of Binary Tree

Difficulty: Easy | Acceptance: 78.10% | Paid: No Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

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.

• Examples
• Constraints
• Recursive Depth-First Search
• Iterative Depth-First Search
• Breadth-First Search

Examples

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3
Explanation: The longest path is 3 -> 20 -> 15 or 3 -> 20 -> 7.

Example 2:

Input: root = [1,null,2]
Output: 2

Constraints

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

Recursive Depth-First Search

Intuition The maximum depth of a tree is the maximum depth of its left or right subtree plus one for the current node. This naturally leads to a recursive solution where we traverse down to the leaf nodes.

Steps

• If the root is null, return 0 (base case).
• Recursively calculate the depth of the left subtree.
• Recursively calculate the depth of the right subtree.
• Return 1 plus the maximum of the left and right depths.

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

Complexity

• Time: O(n) — We visit every node once.
• Space: O(h) — Where h is the height of the tree. This is the space used by the recursion stack. In the worst case (skewed tree), h is O(n).

Iterative Depth-First Search

Intuition We can simulate the recursive call stack using an explicit stack data structure. We store pairs of nodes and their corresponding depths.

Steps

• Initialize a stack with the root node and depth 1.
• While the stack is not empty, pop a node and its depth.
• Update the maximum depth found so far.
• If the node has children, push them onto the stack with their depth incremented by 1.

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        stack = [(root, 1)]
        max_depth = 0
        
        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

Complexity

• Time: O(n) — We visit every node once.
• Space: O(h) — The stack can grow to the height of the tree in the worst case.

Breadth-First Search

Intuition We traverse the tree level by level. The number of levels we traverse corresponds to the maximum depth.

Steps

• Initialize a queue with the root node.
• While the queue is not empty, increment the depth counter.
• Process all nodes currently in the queue (this represents one level).
• Add the children of these nodes to the queue for the next level.

from collections import deque

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

Complexity

• Time: O(n) — We visit every node once.
• Space: O(w) — Where w is the maximum width of the tree. In the worst case (a complete binary tree), the last level holds n/2 nodes, so space is O(n).