Find the Depth of a Binary Tree: Recursive, BFS, Iterative DFS

Find the Depth (Height) of a Binary Tree: Recursive, Iterative BFS, and Iterative DFS

Finding the depth (also called height or maximum depth) of a binary tree is one of the simplest and most-frequently-asked tree problems at coding interviews. It’s LeetCode #104 and appears as the warm-up tree question at most FAANG and AI-lab interviews. The recursive solution is a one-liner, but interviewers use it to test whether you understand recursion fluently and whether you can convert to iterative variants on demand. This guide covers all three standard approaches with working code, the depth-vs-height naming question, and follow-ups.

Problem Statement

Given the root of a binary tree, return its maximum depth. The maximum depth is the number of nodes along the longest path from the root down to the farthest leaf node.

Examples:

• Tree: 3 → (9, 20 → (15, 7)) → depth = 3
• Empty tree (root=None) → depth = 0
• Single node → depth = 1

A note on terminology

“Depth” and “height” are sometimes used interchangeably; sometimes they have specific meanings. Common conventions:

• Height of a tree = longest root-to-leaf path counted in edges (so a single-node tree has height 0).
• Depth of a tree = longest root-to-leaf path counted in nodes (so a single-node tree has depth 1). LeetCode #104 uses this convention.
• Depth of a node = number of edges from root to that node.

For interview purposes, default to LeetCode’s convention (count nodes, single node = 1) unless the interviewer specifies otherwise. If unclear, ask.

Approach 1: Recursive DFS (Standard Answer)

The depth of a tree equals 1 plus the maximum depth of its subtrees. An empty tree has depth 0.

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


def max_depth(root: TreeNode) -> int:
    """O(n) time, O(h) stack space where h is tree height."""
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))


# Test
root = TreeNode(3,
                TreeNode(9),
                TreeNode(20, TreeNode(15), TreeNode(7)))
print(max_depth(root))  # 3
print(max_depth(None))  # 0
print(max_depth(TreeNode(1)))  # 1

Complexity: O(n) time (visit every node once), O(h) space (recursion stack), where h is the tree height. Worst case h = n for a fully skewed tree.

This is the answer the interviewer expects.

Approach 2: Iterative BFS (Level-Order)

Walk the tree level by level. Increment a counter for each level. Useful when the recursive depth is concerning (very deep trees) or when the interviewer asks for an iterative version.

from collections import deque

def max_depth_bfs(root: TreeNode) -> int:
    """O(n) time, O(w) space where w is max width of tree."""
    if not root:
        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

Complexity: O(n) time, O(w) space where w is the maximum width of the tree. For a balanced tree, w = n/2 at the bottom level; for a skewed tree, w = 1.

Approach 3: Iterative DFS

Use an explicit stack with (node, depth) pairs. Useful when avoiding recursion entirely matters (e.g., pathologically deep trees in non-Python languages, or when the interviewer rules out recursion).

def max_depth_iterative_dfs(root: TreeNode) -> int:
    """O(n) time, O(h) space."""
    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: O(n) time, O(h) space (the stack holds at most O(h) entries on a single path).

Common Variations

Minimum depth

(LeetCode #111) Find the shortest root-to-leaf path. Tricky: a leaf is a node with no children, so a node with one child is not a leaf and shouldn’t be counted as having depth 1 if its other subtree is empty.

def min_depth(root: TreeNode) -> int:
    """O(n) time, O(h) space."""
    if not root:
        return 0
    if not root.left:
        return 1 + min_depth(root.right)
    if not root.right:
        return 1 + min_depth(root.left)
    return 1 + min(min_depth(root.left), min_depth(root.right))

BFS is often more efficient for minimum depth — return as soon as you hit the first leaf.

Diameter of a tree

(LeetCode #543) The longest path between any two nodes (may not pass through root). At each node, the longest path through it equals (left depth) + (right depth). Compute via post-order traversal in O(n).

Balanced tree check

(LeetCode #110) A tree is height-balanced if every node’s left and right subtree heights differ by at most 1. Compute via post-order returning either the height or a sentinel “unbalanced” value.

N-ary tree depth

(LeetCode #559) Each node has a list of children rather than left / right. Same recursive structure: 1 + max depth of any child.

class NaryNode:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children or []


def max_depth_nary(root: NaryNode) -> int:
    if not root:
        return 0
    if not root.children:
        return 1
    return 1 + max(max_depth_nary(c) for c in root.children)

Common Mistakes

• Off-by-one between height and depth conventions. Always confirm the convention. LeetCode counts nodes (root has depth 1); some textbooks count edges (root has height 0).
• Not handling the empty tree. Returning 1 for None is the most common bug. Empty tree has depth 0 by convention; check root before recursing.
• Iterative BFS forgetting to size the level. Each level needs a snapshot of the queue size before popping; appending children mid-iteration corrupts the per-level count.
• Treating min_depth like max_depth with min instead of max. A node with one None child should not contribute “depth 1” to the min computation. Walk only the side that has a child if the other is None.
• Accidentally O(n²). Some “naive” recursive depth implementations recompute heights repeatedly (e.g., naive balanced-tree check). The correct pattern returns height in a single post-order pass.

Frequently Asked Questions

See also: Serialize and Deserialize a Binary Tree • Detect a Cycle in a Linked List • Two Sum: Find a Pair in an Array

function maxDepth(root) {
    // Base case: empty tree
    if (root === null) {
        return 0;
    }

    // Recursive case
    let leftDepth = maxDepth(root.left);
    let rightDepth = maxDepth(root.right);

    return 1 + Math.max(leftDepth, rightDepth);
}

// Even more concise version
function maxDepthConcise(root) {
    if (!root) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

// Test tree:
//       1
//      / 
//     2   3
//    /
//   4

let tree = {
    val: 1,
    left: {
        val: 2,
        left: { val: 4, left: null, right: null },
        right: null
    },
    right: { val: 3, left: null, right: null }
};

console.log(maxDepth(tree));  // 3

function maxDepthIterative(root) {
    if (!root) return 0;

    let queue = [root];
    let depth = 0;

    while (queue.length > 0) {
        let levelSize = queue.length;
        depth++;

        // Process all nodes at current level
        for (let i = 0; i < levelSize; i++) {
            let node = queue.shift();

            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }

    return depth;
}