EasyBlind75TreeDFSBFS

Maximum Depth of Binary Tree

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

Examples

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

The longest path is 3->20->15, depth is 3.

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

The longest path is 1->2, depth is 2.

Constraints

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

Approaches

Use BFS and count the number of levels.

CodeT: O(n) | S: O(n)
from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_depth(root):
    if not root:
        return 0
    depth = 0
    queue = deque([root])
    while queue:
        depth += 1
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return depth

Recursively find depth of left and right subtrees, return max + 1.

CodeT: O(n) | S: O(h)
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

Use an iterative DFS with a stack, tracking depth for each node.

Diagram

Tree: 3->9, 3->20->15, 3->20->7 DFS: (3,1)->(9,2)->(20,2)->(15,3)->(7,3) max_d = 3
CodeT: O(n) | S: O(h)
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_depth(root):
    if not root:
        return 0
    stack = [(root, 1)]
    max_d = 0
    while stack:
        node, depth = stack.pop()
        max_d = max(max_d, depth)
        if node.left:
            stack.append((node.left, depth + 1))
        if node.right:
            stack.append((node.right, depth + 1))
    return max_d

Complexity Comparison

BFS - Level Order
T: O(n)S: O(n)

Use BFS and count the number of levels.

DFS - Recursive
T: O(n)S: O(h)

Recursively find depth of left and right subtrees, return max + 1.

DFS - Iterative
T: O(n)S: O(h)

Use an iterative DFS with a stack, tracking depth for each node.

Common Mistakes

Confusing depth with height (they are the same for binary trees)

Not handling the empty tree case (should return 0)

Using level-order traversal when recursion is simpler

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems