Description

Given the root of a binary tree, return its maximum depth.

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

A leaf node is a node that does not have any children.

Example 1

Input: root = [1,2,3,null,null,4]

Output: 3

The longest path is:

1 → 3 → 4

This path contains three nodes, so the maximum depth is 3.

Example 2

Input: root = []

Output: 0

An empty tree does not contain any nodes, so its depth is 0.

Constraints

0 <= number of nodes in the tree <= 100
-100 <= Node.val <= 100

Approach 1: Recursive Depth-First Search

The most natural way to solve this problem is with recursion.

For every node, we calculate:

The depth of its left subtree
The depth of its right subtree

We take the greater of the two depths and add 1 for the current node.

The recurrence is:

depth(node) = 1 + max(depth(node.left), depth(node.right))

If the current node is None, its depth is 0.

Code

from typing import Optional


# 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: Optional[TreeNode]) -> int:
        if not root:
            return 0

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

How It Works

Consider the following tree:

Starting at node 1, the function asks for the depth of the left and right subtrees.

For node 2:

left depth = 0
right depth = 0

Therefore:

depth of node 2 = 1 + max(0, 0) = 1

For node 4:

depth of node 4 = 1

For node 3:

left depth = 0
right depth = 1

Therefore:

depth of node 3 = 1 + max(0, 1) = 2

Finally, for node 1:

left depth = 1
right depth = 2

Therefore:

depth of node 1 = 1 + max(1, 2) = 3

Why We Add

`1`

The recursive calls calculate the depth below the current node.

The 1 represents the current node itself.

1 + max(left_depth, right_depth)

Without adding 1, the current node would not be included in the path length.

Complexity

Time Complexity

O(n)

Every node is visited exactly once.

Space Complexity

O(h)

Here, h is the height of the tree.

The recursive call stack stores one function call for each node along the current path.

For a balanced tree:

O(log n)

For a completely unbalanced tree:

O(n)

Approach 2: Breadth-First Search

Breadth-first search processes the tree one level at a time.

We use a queue to store the nodes waiting to be processed.

Each time we finish processing one complete level, we increase the depth by 1.

Code

from typing import Optional
from collections import deque


class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        level = 0
        queue = deque([root])

        while queue:
            for _ in range(len(queue)):
                node = queue.popleft()

                if node.left:
                    queue.append(node.left)

                if node.right:
                    queue.append(node.right)

            level += 1

        return level

How It Works

We begin by adding the root node to the queue:

queue = deque([root])

For the following tree:

The queue changes like this:

Level 1

Queue: [1]

We remove node 1 and add its children:

Queue: [2, 3]

After processing the level:

level = 1

Level 2

At the beginning of the iteration:

Queue: [2, 3]

We remove exactly two nodes because the queue currently contains two nodes.

After processing nodes 2 and 3:

Queue: [4]
level = 2

Level 3

Queue: [4]

After processing node 4:

Queue: []
level = 3

The queue is now empty, so we return 3.

Why We Use

`range(len(queue))`

This line is important:

for _ in range(len(queue)):

At the start of each while loop iteration, len(queue) represents the number of nodes in the current level.

New child nodes may be added to the queue while the loop is running, but they should not be processed until the next level.

Python evaluates len(queue) before the for loop starts. Therefore, only the nodes that were already in the queue are processed during the current iteration.

Why `deque` Is Used

We repeatedly remove nodes from the front of the queue:

node = queue.popleft()

A deque supports removing from the front in:

O(1)

Removing the first element from a normal Python list would take:

O(n)

because all remaining elements would need to shift one position.

Complexity

Time Complexity

O(n)

Every node is added to and removed from the queue once.

Space Complexity

O(w)

Here, w is the maximum width of the tree.

In the worst case, the queue may contain an entire level of the tree, resulting in:

O(n)

space.

Approach 3: Iterative Depth-First Search

We can also perform depth-first search iteratively using a stack.

The stack stores both:

The node that should be processed
The depth of that node

Each stack entry has the form:

(node, depth)

Code

from typing import Optional

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

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

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

            if node.left:
                stack.append((node.left, depth + 1))

            if node.right:
                stack.append((node.right, depth + 1))

        return result

How It Works

We begin by placing the root in the stack with a depth of 1:

stack = [(root, 1)]

The root has depth 1 because it is the first node in the path.

On every iteration, we remove the most recently added item:

node, depth = stack.pop()

We then update the greatest depth seen so far:

result = max(result, depth)

Finally, we add the node’s children with a depth that is one greater:

stack.append((node.left, depth + 1))
stack.append((node.right, depth + 1))

Example

Consider:

The stack begins as:

[(1, 1)]

After processing node 1, we add its children:

[(2, 2), (3, 2)]

Because a stack follows last-in, first-out order, node 3 is processed next.

After processing node 3, its children are added:

[(2, 2), (None, 3), (4, 3)]

When node 4 is processed:

result = max(2, 3)

Therefore:

result = 3

Why Store the Depth in the Stack?

A normal recursive DFS automatically remembers the current depth through the recursive call stack.

With an iterative DFS, we do not have recursive function calls to track that information.

Therefore, we manually store the depth alongside each node:

(node, depth)

This allows us to know how far each node is from the root when it is removed from the stack.

Why Can Tuples Be Unpacked?

The stack contains tuples such as:

(root, 1)

When we write:

node, depth = stack.pop()

Python removes one tuple from the stack and unpacks its two values.

For example:

item = (root, 1)
node, depth = item

This assigns:

node = root
depth = 1

Lists could also be used:

stack = [[root, 1]]

Both lists and tuples can be unpacked.

A tuple is slightly more appropriate here because each stack entry is a fixed pair of values that does not need to be modified.

Complexity

Time Complexity

O(n)

Every node is processed once.

Space Complexity

O(h)

The stack stores nodes along the DFS traversal.

For a balanced tree:

O(log n)

For a completely unbalanced tree:

O(n)

Because this implementation temporarily adds None children to the stack, it may store some additional entries, but the overall complexity remains the same.

Comparing the Three Approaches

Approach	Data structure	Time	Space	Main idea
Recursive DFS	Recursion stack	`O(n)`	`O(h)`	Find the greater subtree depth
BFS	Queue	`O(n)`	`O(w)`	Count the number of levels
Iterative DFS	Explicit stack	`O(n)`	`O(h)`	Track each node with its depth

Here:

n is the number of nodes
h is the height of the tree
w is the maximum width of the tree

Which Approach Should I Use?

The recursive DFS solution is usually the best solution to present first.

It is concise and directly expresses the recursive structure of a binary tree:

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

The BFS solution is useful when thinking in terms of tree levels.

The iterative DFS solution is useful when recursion is not allowed or when the tree may be deep enough to cause a recursion-depth issue.

Improved Iterative DFS Version

The original iterative DFS solution adds if not root to the start of the code.

if not root:
    return 0

We can avoid it by checking the node before updating the result.

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:

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

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

            if node:
                result = max(result, depth)

                stack.append((node.left, depth + 1))
                stack.append((node.right, depth + 1))

        return result

Both versions are correct.

Key Takeaways

The maximum depth of a binary tree can be found using several traversal strategies.

With recursive DFS, the answer for each node is:

1 + the greater depth of its two subtrees

With BFS, the answer is the number of levels processed.

With iterative DFS, each node is stored together with its current depth.

All three approaches visit every node and therefore have a time complexity of:

O(n)

The recursive DFS solution is generally the simplest and most natural solution for this problem.

Description

Example 1

Example 2

Constraints

Approach 1: Recursive Depth-First Search

Code

How It Works

Why We Add

1

Complexity

Time Complexity

Space Complexity

Approach 2: Breadth-First Search

Code

How It Works

Level 1

Level 2

Level 3

Why We Use

range(len(queue))

Why deque Is Used

Complexity

Time Complexity

Space Complexity

Approach 3: Iterative Depth-First Search

Code

How It Works

Example

Why Store the Depth in the Stack?

Why Can Tuples Be Unpacked?

Complexity

Time Complexity

Space Complexity

Comparing the Three Approaches

Which Approach Should I Use?

Improved Iterative DFS Version

Key Takeaways

Subscribe to Sharooq

Subscribe to Sharooq

`1`

`range(len(queue))`

Why `deque` Is Used