Maximum Depth of Binary Tree

Easy · Trees · Explanation and code example

Breadth First Search

How it works

Breadth-First Search (BFS) processes the tree level by level.
This makes it a perfect fit for computing the maximum depth because:

  • Every iteration of BFS processes one entire level of the tree.
  • So each completed level corresponds to increasing the depth by 1.

We simply count how many levels we traverse until the queue becomes empty.

Think of the queue like a moving frontier:

  • Start with the root → depth = 1
  • Add its children → depth = 2
  • Add their children → depth = 3
  • Continue until no nodes remain.

The number of BFS layers processed is exactly the depth of the tree.

Steps

  1. If the tree is empty (root == null), return 0.
  2. Initialize a queue and push the root.
  3. Initialize level = 0.
  4. While the queue is not empty:
    • Determine the number of nodes at the current level (size = len(queue)).
    • Process all size nodes:
      • Pop from the queue.
      • Push their left and right children if they exist.
    • After processing the entire level, increment level.
  5. Return level when the queue becomes empty.

Complexity

  • Time complexity: O(n)
  • Space complexity: O(n)

Things to watch for

Confusing Depth with Height

Depth is measured from the root down (root has depth 1 or 0 depending on convention), while height is measured from the leaves up. The maximum depth of a tree equals its height when counting from root. Be consistent with whether you start counting at 0 or 1.

Forgetting to Handle the Empty Tree Case

An empty tree (null root) has a depth of 0. Failing to check for this base case before accessing node properties will cause a null pointer exception.

Python code example

from typing import Optional
from collections import deque

# 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:
        q = deque()
        if root:
            q.append(root)

        level = 0
        while q:
            for i in range(len(q)):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            level += 1
        return level

C++ code example

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue<TreeNode*> q;
        if (root != nullptr) {
            q.push(root);
        }

        int level = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                if (node->left != nullptr) {
                    q.push(node->left);
                }
                if (node->right != nullptr) {
                    q.push(node->right);
                }
            }
            level++;
        }
        return level;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations