Skip to content

Volume ITechnology

4.14.2 — Maximum Depth of Binary Tree ​

LeetCode 104 · Easy · ★ Blind 75

The problem ​

You are given the root of a binary tree. Return its maximum depth: the number of nodes on the longest path from the root down to a leaf. A leaf is a node with no children.

     3
   /   \
  9    20        →  3   (the path 3 → 20 → 15 has three nodes)
      /   \
    15     7

An empty tree has depth 0. A single node has depth 1. The tree has up to 10,000 nodes.

What the problem is really asking ​

Stand at the root and ask: "how deep is the tree below me?" You cannot answer straight away. But you can answer if your two children tell you how deep their own subtrees are. Then:

\text{depth}(\text{node}) = 1 + \max\big(\text{depth}(\text{left}),\ \text{depth}(\text{right})\big)

Read it as "the depth of a node is one (for the node itself) plus the depth of its deeper child". An empty tree has depth 0, and that is where the recursion stops.

So the real question is: can each node work out its depth from its children's depths? Yes, and that sentence is the code.

This kind of calculation is called post-order. A node cannot give its answer until both children have given theirs. Answers flow upward, from the leaves to the root. Most tree problems that return a number work this way.

The brute force ​

There is no slower "obvious" method worth comparing. Any correct method must look at every node, because the deepest leaf could be anywhere. The recursive answer looks at each node once.

The solution ​

python
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:                                                       # (1)
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))  # (2)
ts
function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;                                                     // (1)
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));          // (2)
}

Line by line ​

(1) An empty tree has depth 0. This is the base case that ends the recursion. It also makes a leaf come out right: a leaf's two children are both missing, so it gets 1 + \max(0, 0) = 1, and a single node is indeed a tree of depth 1.

(2) One for this node, plus the deeper child. Ask both children for their depths. Trust those calls to be correct. Take the bigger one and add 1 for the current node.

Trace ​

Take the tree above. Each row is one call returning its answer. The calls finish from the bottom up.

Call onLeft child's depthRight child's depthReturns
90 (none)0 (none)1 + 0 = 1
15001
7001
201 (from 15)1 (from 7)1 + 1 = 2
31 (from 9)2 (from 20)1 + 2 = 3

Complexity, derived ​

Time. Each node is visited once, and each visit does one comparison and one addition. So O(n).

Space. The waiting recursive calls form a chain as long as the tree's height, h. So O(h). That is about \log_2 n for a balanced tree, and n for a tree shaped like a straight line.

Edge cases ​

  • Empty tree. Line (1) returns 0.
  • One node. Returns 1.
  • A straight line of nodes, each with one child. The depth is the number of nodes. The recursion is that many calls deep.

Two versions without recursion ​

Both are worth being able to write, because the choice between them is a real one.

Breadth-first: count the levels. Visit the tree one level at a time. The number of levels is the depth.

python
from collections import deque

def maxDepth(self, root):
    if not root:
        return 0
    queue = deque([root])
    depth = 0
    while queue:
        depth += 1                          # starting a new level
        for _ in range(len(queue)):         # exactly the nodes on this level
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return depth

The for _ in range(len(queue)) line is the important one, and it comes back throughout this chapter. len(queue) is measured before the inner loop starts. At that moment, the queue holds exactly the nodes on the current level. So the inner loop handles exactly those nodes. Children added during the loop belong to the next level and wait for the next round. Without this line, you could not tell where one level ends and the next begins.

Depth-first with your own stack. Push pairs of (node, its depth), pop them one at a time, push the children with depth plus one, and keep track of the biggest depth seen.

Which kind of walk, and when ​

This choice runs through the whole chapter, so here it is once.

  • A depth-first walk (DFS) goes all the way down one branch before trying the next. Use it when the answer depends on whole subtrees: depths, sums, paths, checks. It needs O(h) memory, the height.
  • A breadth-first walk (BFS) visits the tree level by level. Use it when the answer depends on levels, or when you want the shallowest answer and can stop early. It needs O(w) memory, where w is the widest level.

In a balanced tree, the bottom level holds about half of all the nodes. So BFS can need O(n) memory where DFS needs only O(\log n). In a tree shaped like a line, it is the other way round. That trade is why both exist.

Variations you will meet ​

  • Minimum Depth of Binary Tree. Almost the same, with one trap. A node with only one child is not a leaf. So 1 + min(left, right) would wrongly count the missing child's depth of 0. Breadth-first is cleaner there, because you can stop at the first leaf you meet.
  • Balanced Binary Tree. Depth again, but each node must also report whether its subtree is balanced. See 4.14.4.
  • Diameter of Binary Tree. The longest path anywhere in the tree, worked out from depths. See 4.14.3.

The general lesson: when a node's answer can be built from its children's answers, return those answers upward and combine them at each node.

What the interviewer will push on ​

"Can you do it without recursion?" Yes, breadth-first by counting levels, or depth-first with a stack of (node, depth) pairs.

"Which uses less memory, DFS or BFS?" It depends on the shape. DFS uses the height and BFS uses the width. For a balanced tree, DFS wins.

"Why does the base case return 0, not 1?" Because it handles a missing node, not a leaf. A leaf then gets 1 from the formula.

One thing to volunteer: explain the len(queue) trick in the breadth-first version. It is the key to every level-by-level tree problem.

Next: 4.14.3 Diameter of Binary Tree. Where the number you pass upward is not the answer the problem asks for.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet