What is the brute force approach and complexity for Maximum Depth of Binary Tree?

Walk the tree one level at a time with a queue; the number of levels is the depth with time complexity O(N) and space complexity O(W).

What is the optimal approach and complexity for Maximum Depth of Binary Tree?

Each node returns 1 + the larger of its children's answers; an empty child returns 0 with optimal time complexity O(N) and space complexity O(H).

How do you identify the pattern for Maximum Depth of Binary Tree?

Look for key signals in the prompt: "depth of the tree" indicates The longest root-to-leaf path. It is the larger side, not the sum of the two sides.; "root with two subtrees" indicates A tree is one root and two smaller trees, so the answer for the whole tree can be built from the answers for the parts.; "empty tree" indicates The base case: no nodes means 0 levels..

Maximum Depth of Binary Tree

Easy·LeetCode #104Basic Anchor

LeetCode

Jump:

30-Second Mental ModelTree DFS, traversal: each child returns its depth, and the parent combines the two answers

Complexity:O(N)→O(N)

Key Insight

Ask both children how deep their subtrees are. The deeper side plus this node is the depth at this node. An empty child returns 0, so a leaf returns 1 + max(0, 0) = 1. The base case is the empty tree, which is 0 levels.

Core Validity Invariant

The depth of a subtree is 1 + the larger child depth, and an empty subtree has depth 0. That one rule covers every node, leaves included.

Problem

You are given the root of a binary tree. Return its depth: the number of nodes on the longest path from the root down to a leaf.

An empty tree has depth 0.

Input

The root of a binary tree. The tree may be empty.

Output

A single number: the depth of the tree.

Example 1

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

Output: 3

The longest path is 3 → 20 → 15 (or 3 → 20 → 7). That path has 3 nodes.

Example 2

Input: root = [1, null, 2]

Output: 2

The only path is 1 → 2, which has 2 nodes.

Example 3

Input: root = []

Output: 0

There are no nodes, so there are no levels.

Constraints

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

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
How many nodes are on a path that is just one node? What depth should that give?
2.
If I know the depth of the left subtree and the depth of the right subtree, can I get the depth of the whole tree?
3.
Only the longer side decides the longest path. Do I need both sides' numbers, or just the bigger one?
4.
What should an empty child contribute to the depth: 0 or 1? Why?
5.
Does this question count every node, or only the nodes on one longest path?

Brute force approach

Idea

Put the root in a queue. Each round pops every node that is in the queue at the start of the round, so each round handles exactly one whole level, and pushes their children. The number of rounds is the depth.

Thinking process

1
The depth is just the number of levels, so count the levels directly.
2
On [3, 9, 20, null, null, 15, 7]: round 1 pops 3 (queue size 1), round 2 pops 9 and 20 (size 2), round 3 pops 15 and 7 (size 2). Then the queue is empty. That is 3 rounds.
3
The round must pop exactly the nodes that were in the queue when it started. If it kept popping, the children it just pushed would be counted in the same round.
4
Stop when the queue is empty.

Visual

Each round pops exactly one level, so the number of rounds is the depth. Green nodes were already popped; blue is the node popped now. The queue is shown front (left) to back (right).

Counting levels with a queueroot = [3, 9, 20, null, null, 15, 7]step 1/10

tree

queue

▲front

BFS

round: —
nodes in this round: —
levels: 0

Start: the queue holds the root

Put the root in the queue. Each round empties one whole level, so counting rounds counts levels.

Code & Implementation

brute.cpp

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        queue<TreeNode*> q;
        q.push(root);
        int levels = 0;
        while (!q.empty()) {
            // Everything in the queue right now is one full level.
            size_t levelSize = q.size();
            for (size_t i = 0; i < levelSize; i++) {
                TreeNode* node = q.front();
                q.pop();
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            levels++;
        }
        return levels;
    }
};

import java.util.ArrayDeque;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        int levels = 0;
        while (!q.isEmpty()) {
            // Everything in the queue right now is one full level.
            int levelSize = q.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = q.poll();
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
            levels++;
        }
        return levels;
    }
}

from collections import deque
from typing import Optional, List, Dict, Tuple

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
        q = deque([root])
        levels = 0
        while q:
            # Everything in the queue right now is one full level.
            level_size = len(q)
            for _ in range(level_size):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            levels += 1
        return levels

export class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.left = (left === undefined ? null : left);
        this.right = (right === undefined ? null : right);
    }
}

export function maxDepth(root: TreeNode | null): number {
    if (!root) return 0;
    const q: TreeNode[] = [root];
    let levels = 0;
    while (q.length > 0) {
        // Everything in the queue right now is one full level.
        const levelSize = q.length;
        for (let i = 0; i < levelSize; i++) {
            const node = q.shift()!;
            if (node.left) q.push(node.left);
            if (node.right) q.push(node.right);
        }
        levels++;
    }
    return levels;
}

Complexity

Time O(N)Space O(W)

Time is the same as the optimal, O(n): every node is pushed and popped once. The difference is memory. The queue holds one whole level, so the extra space is O(W), the width of the widest level. For a full tree that is about n / 2. The recursion below only keeps the current path, O(H). Neither is always smaller: on a chain (one node per level), BFS holds one node at a time while the recursion goes n calls deep.

Optimized approach

Idea

Start from brute force

BFS counts levels by walking the tree one level at a time, and the queue holds a whole level at once.

Find the repeated work

Nothing is repeated. Both approaches touch every node exactly once. What changes is how much memory each one keeps while it works.

Define the state — what variables do I need?

node: The root of the subtree this call is measuring.
left, right: The depths of the two child subtrees, returned by the calls below.
return value: The depth of this subtree: 0 for an empty subtree, otherwise 1 + the larger of left and right.

Define validity

The depth of a subtree is 1 + the larger child depth, and an empty subtree has depth 0. That one rule covers every node, leaves included.

Define the transitions — when does each pointer move, and why is it safe?

node is null

return 0

No node means no levels. This base case is what makes a leaf come out as 1 + max(0, 0) = 1.

node is not null

return 1 + max(depth(left), depth(right))

The longest path from this node goes down one side. The two calls give both depths, and the larger one wins.

What does the current window add to the answer?

Each node returns its own depth to its parent. The root's return value is the answer, because it is the longest path from the top.

Code & Implementation

optimal.cpp

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;   // an empty subtree adds no levels
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }
};

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0; // an empty subtree adds no levels
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

from typing import Optional, List, Dict, Tuple

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  # an empty subtree adds no levels
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

export class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.left = (left === undefined ? null : left);
        this.right = (right === undefined ? null : right);
    }
}

export function maxDepth(root: TreeNode | null): number {
    if (!root) return 0; // an empty subtree adds no levels
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Complexity

Time O(N)Space O(H)

Each node is called once and does constant work, so the time is O(n), the same as the BFS. The space is the call stack: one frame per level on the current path, so O(h), the height. For a balanced tree that is about log2(n), much less than BFS's width. For a chain it is n, which is worse than BFS.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Walk the tree one level at a time with a queue; the number of levels is the depth	O(N)	O(W)
Optimal	Each node returns 1 + the larger of its children's answers; an empty child returns 0	O(N)	O(H)

Why does this belong to this pattern?

Clues in the problem statement

“depth of the tree”The longest root-to-leaf path. It is the larger side, not the sum of the two sides.
“root with two subtrees”A tree is one root and two smaller trees, so the answer for the whole tree can be built from the answers for the parts.
“empty tree”The base case: no nodes means 0 levels.

depth(node) = 1 + max(depth(left), depth(right))+depth(null) = 0+answer = depth(root)→Tree DFS, traversal: each child returns its depth, and the parent combines the two answers

This is the first and simplest tree question: the answer for a node comes from the answers of its children. The recursion visits the children first and combines the results on the way back up. Same Tree and Symmetric Tree keep the same walk but compare two trees instead of combining one, and that is where the traversal sub-pattern changes.

Don't make this mistake

Returning 1 for an empty node

✗ if (!root) return 1;

✓ if (!root) return 0;

The two empty children of a leaf would each count as one level, so a single node looks like it has a level below it. On [1] the wrong version returns 2. An empty tree returns 1 as well instead of 0. Empty means zero levels.

Adding the two sides instead of taking the larger one (pattern confusion: that counts nodes)

✗ return 1 + maxDepth(root->left) + maxDepth(root->right);

✓ return 1 + max(maxDepth(root->left), maxDepth(root->right));

This counts every node, so it returns the size of the tree, not its depth. On [3, 9, 20, null, null, 15, 7] the wrong version returns 5 (the number of nodes), while the depth is 3. A depth is a longest path, so only the deeper side counts.

Counting nodes instead of levels in BFS

✗ while (!q.empty()) { TreeNode* node = q.front(); q.pop(); levels++; ... }

✓ size_t levelSize = q.size(); for (size_t i = 0; i < levelSize; i++) { ... }

Adding one per popped node counts nodes. On [3, 9, 20, null, null, 15, 7] that gives 5. A round has to pop exactly one level, so the size of the queue is read once before the loop, and only then is the count increased.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Tree DFS translate into production architectures and low-level memory mechanics.

LLD Architecture