Skip to main content
DSA patterns

Maximum Depth of Binary Tree

easyTrees Must-doTCSInfosysWipro

Problem statement

You are given the root of a binary tree. Return its maximum depth: the number of nodes along the longest path from the root down to the farthest leaf. A leaf is a node with no children. An empty tree (a null root) has depth 0.

This is the same question you'd ask about any tree-shaped structure: how deep does a directory tree go, how many hops does the deepest dependency chain have, how nested is a parsed config. Here the tree is given directly as a binary tree of nodes.

Examples

Example 1

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

Output: 3

Explanation: the longest root-to-leaf path is 3 → 20 → 15 (or 3 → 20 → 7), which passes through 3 nodes.

Example 1

Example 2

Input: root = [1,null,2]

Output: 2

Explanation: node 1 has no left child, so the only path is 1 → 2, which passes through 2 nodes.

Hints

Hint 1: What does the depth of a tree have to do with the depth of its left and right subtrees? Try writing the answer for a whole tree in terms of the answer for its two children.

Approach

Optimal: Iterative BFS, level order

Intuition

Instead of recursing down to the leaves and combining results on the way back up, process the tree one entire level at a time using a queue, the same way you would explore a graph breadth-first. Each time the current level is fully processed and every one of its children has been queued for the next level, add 1 to a depth counter. Once the queue empties, that counter is exactly the number of levels visited, which is the tree's maximum depth. This gives the same answer as the recursive version without using the call stack, trading it for an explicit queue.

Steps

  1. If the root is null, return 0 immediately.
  2. Put the root in a queue and set depth = 0.
  3. While the queue is not empty, note how many nodes are in it right now. That count is exactly one level.
  4. Remove that many nodes one by one, and for each, add its left and right children to the queue if they exist.
  5. After that whole level has been processed, add 1 to depth.
  6. Once the queue is empty, return depth.

Dry run

root = [3,9,20,null,null,15,7], same tree as before.

level queue at start of level nodes processed children enqueued depth after level
1 [3] 3 9, 20 1
2 [9, 20] 9, 20 15, 7 (9 has none) 2
3 [15, 7] 15, 7 none (both leaves) 3

The queue is now empty. Result: 3, matching Example 1.

Edge cases: an empty tree returns 0 straight from the initial null check, before the queue is ever touched.

Complexity

Time O(n) - Every node is enqueued and dequeued exactly once over the whole traversal. The work per node (checking and pushing its children) is O(1). So the total work is O(n).

Space O(n) - The queue can hold an entire level's worth of nodes at once. For a tree with `n` nodes, the widest level can hold up to roughly `n/2` nodes (for example the bottom level of a complete binary tree). So the queue's worst-case size is proportional to `n`, not to the tree's height.

from collections import deque
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 root is None:
            return 0
        queue = deque([root])
        depth = 0
        while queue:
            level_size = len(queue)
            for _ in range(level_size):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            depth += 1
        return depth


def build_tree(values: list) -> Optional[TreeNode]:
    """Builds a tree from LeetCode's level-order array, where None marks a missing child."""
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue, i = deque([root]), 1
    while queue and i < len(values):
        node = queue.popleft()
        if i < len(values):
            if values[i] is not None:
                node.left = TreeNode(values[i])
                queue.append(node.left)
            i += 1
        if i < len(values):
            if values[i] is not None:
                node.right = TreeNode(values[i])
                queue.append(node.right)
            i += 1
    return root


if __name__ == "__main__":
    print(Solution().maxDepth(build_tree([3, 9, 20, None, None, 15, 7])))
    print(Solution().maxDepth(build_tree([1, None, 2])))
RecapThe whole problem in a few lines, for the night before
  • Spot it: "return the depth/height of a binary tree", a single number for how deep the tree goes
  • Idea: depth of a node = 1 + the deeper of its two children's depths; an empty subtree has depth 0
  • Cost: O(n) time either way; O(h) space for recursive DFS (call stack), O(n) space for iterative BFS (widest level)
  • Trap: an empty tree returns 0, not 1, and a single-node tree is depth 1, not 0
  • Remember: the iterative BFS version avoids the call stack, which matters for a very deep, narrow tree that could overflow the recursion stack

Interview follow-ups

  • Find the minimum depth instead, the shortest root-to-leaf path.

    The recursive structure is almost the same, but the base case needs care. If a node has only one child, you must recurse into that child rather than treating the missing child as depth 0, or you would report a shorter path through a node that is not actually a leaf. So the rule becomes: if a node has both children, return 1 + min(left, right); if it has only one child, return 1 + the depth of whichever child exists; a true leaf (no children) returns 1. It is the same O(n) time, and the BFS version is even better here because it can return the moment it first reaches any leaf.

  • The tree is read from a stream and does not fit in memory as a nested structure, so you only get parent-child edges one at a time.

    Build depth information step by step instead of recursing over a finished tree. Keep a map from node id to depth, and set a node's depth to its parent's depth plus 1 as soon as the parent's depth is known. If edges can arrive out of order, hold the edges whose parent has not been seen yet in a pending list and resolve them later. The running maximum over all resolved depths is the answer. This replaces the O(h) recursion stack with O(n) map storage, but never needs the whole tree in memory as linked nodes.

  • Instead of just the depth, return the actual longest path (the list of node values along it).

    Have each recursive call return both a depth and the path that achieves it, instead of just a number. At each node, take the longer of the two children's paths and put the node's own value in front of it. Every call still does a constant amount of extra work beyond the recursive calls, plus the cost of building the path, so the total is O(n) time in the common case and up to O(n · h) if you copy lists naively. Only the winning path is kept at each step, so memory stays far below what the brute force that stores every path needs.

Frequently asked questions

Both the recursive DFS and the iterative BFS visit every node exactly once and do O(1) work per node, so neither is slower than the other. They differ in how they use memory (the call stack versus an explicit queue), not in how much work they do. That is why both are shown as equally good optimal solutions, and only the "collect every path" version is called brute force.

It builds data you never need. To read one number, the longest length, it copies a full path for every leaf and keeps them all in memory. The recursive version gets the same number by passing only a depth back up from each child. If you start with the path idea in an interview, say that you only need the lengths, and the optimal version follows naturally.

When the tree could be very deep and very unbalanced, such as a linked-list-shaped tree with thousands of nodes that each have only one child. The recursive version's call stack grows one frame per level and can hit a stack-overflow limit long before it hits any language's array-size limit. The BFS version's queue grows with the width of the tree instead of its height, so a deep, narrow tree that would blow the recursion stack is no problem for it.

For the recursive version, no. maxDepth(null) returning 0 as the base case means you do not need to check for null before recursing into a child, because the recursive call handles it safely either way. The BFS version does check before adding a child to the queue, but only to avoid pushing null placeholders, which would add unnecessary work later and not change the answer.

Depth and height show up constantly outside of literal binary trees: how many directories deep a filesystem walk goes, how long the longest chain of service dependencies is, how deeply nested a parsed JSON or YAML document is. The recursive "answer equals 1 plus the best of my children's answers" pattern generalizes to any of those tree-shaped structures. Knowing when to switch to an explicit queue instead of recursion matters whenever the structure being walked is not guaranteed to be shallow.

The same idea still works. The depth of a node is still 1 + the maximum depth among all of its children, instead of just two, with the base case unchanged (an empty subtree contributes 0). LeetCode's N-ary Tree Maximum Depth problem is exactly this generalization, and both the recursive and level-order approaches carry over with the loop over two children widened to a loop over however many children the node has.