Max Depth of Binary Tree

You're sitting in a Bloomberg phone screen, and the interviewer opens with a warm-up: "Given a binary tree, find its maximum depth." You know this one. It's the kind of problem that looks trivial on the surface, but your answer reveals whether you actually understand recursion and tree traversal, or just memorized solutions. Getting it right quickly and confidently sets the tone for harder follow-ups like tree balancing and diameter calculation.

TL;DR

The maximum depth of a binary tree is found by recursively computing max(left subtree depth, right subtree depth) + 1, with null nodes returning 0 as the base case. Every node is visited once, so the time complexity is O(n). Space complexity is O(h) where h is the tree height - O(log n) for balanced trees, O(n) for skewed ones. This is one of the cleanest recursive algorithms you'll encounter: three lines of logic, no auxiliary data structures, and it maps directly to how trees are defined.

Why This Problem Matters

Maximum depth of a binary tree is a gateway problem. It tests whether you can think recursively about tree structures, which is a prerequisite for almost every other tree question. Companies like Bloomberg, Amazon, and Microsoft use it to warm up before asking about tree balancing, lowest common ancestors, or serialization. The recursive pattern you learn here - "solve for children, combine the results" - shows up in dozens of tree and divide-and-conquer problems.

Binary Trees: A Quick Refresher

A binary tree is a hierarchical data structure where each node has at most two children, called the left child and right child.

Key properties to keep in mind:

• Root: The topmost node (3 in our example)
• Leaf: A node with no children (9, 15, and 7)
• Depth/Height: The number of nodes on the longest root-to-leaf path
• Subtree: Any node and all its descendants form a subtree

Each node in a standard binary tree definition looks like this:

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
}

This recursive structure - a node pointing to two smaller trees - is exactly why recursive solutions feel natural for tree problems.

Understanding the Problem

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.

For our example tree [3, 9, 20, #, #, 15, 7]:

There are two paths of length 3: 3 -> 20 -> 15 and 3 -> 20 -> 7. The path 3 -> 9 has length 2. So the maximum depth is 3.

Edge Cases to Consider

1. Empty tree (null root): Return 0
2. Single node: Return 1

3. Skewed tree (all nodes on one side): Depth equals the number of nodes

4. Balanced tree: Depth is logarithmic relative to node count

Solution Approach

Think about it this way: if you're standing at the root and you want to know the maximum depth of the tree, you need two pieces of information:

1. The maximum depth of the left subtree
2. The maximum depth of the right subtree

Your depth is then 1 (counting yourself) plus whichever subtree is deeper. And each subtree can answer the same question about itself using the same logic. That is the recursive insight.

The Base Case

When the recursion reaches a null node (past a leaf), there are no nodes to count, so return 0. This is what stops the recursion and starts the "unwinding" phase where results propagate back up.

Here's how the base case works for a leaf node like 9, which has no children:

Both children of node 9 are null, each returning 0. Then max(0, 0) + 1 = 1, which is correct: a single leaf node has depth 1.

The Full Recursion

For the complete tree [3, 9, 20, #, #, 15, 7], here's how the recursion unfolds:

The left subtree rooted at 9 returns 1. The right subtree rooted at 20 returns 2 (since it has children 15 and 7, each at depth 1). Back at the root: max(1, 2) + 1 = 3.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public int maxDepth(TreeNode root) {
    // Base case: null node contributes 0 to depth
    if (root == null) {
      return 0;
    }

    // Recursively compute depth of each subtree
    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);

    // Current node adds 1 to the deeper subtree's depth
    return Math.max(leftDepth, rightDepth) + 1;
  }
}

That's it. Three meaningful lines of logic. The algorithm visits every node exactly once, computing each node's contribution on the way back up from the recursion.

Step-by-Step Trace

For the input [3, 9, 20, #, #, 15, 7]:

1. maxDepth(3) calls maxDepth(9) and maxDepth(20)
2. maxDepth(9) calls maxDepth(null) twice, both return 0. Result: max(0, 0) + 1 = 1
3. maxDepth(20) calls maxDepth(15) and maxDepth(7)
4. maxDepth(15) calls maxDepth(null) twice, both return 0. Result: max(0, 0) + 1 = 1
5. maxDepth(7) calls maxDepth(null) twice, both return 0. Result: max(0, 0) + 1 = 1
6. Back at maxDepth(20): max(1, 1) + 1 = 2
7. Back at maxDepth(3): max(1, 2) + 1 = 3

The answer is 3.

Complexity Analysis

Time Complexity: O(n)

Every node is visited exactly once. At each node, we do constant work: one comparison and one addition. Total operations scale linearly with the number of nodes.

Space Complexity: O(h), where h is the tree height

The space comes from the recursive call stack. Each active recursive call holds a stack frame until its children return.

• Balanced tree: The height is O(log n), so stack depth is O(log n)
• Skewed tree: The height is O(n), so stack depth is O(n)

The worst case is O(n), which matches the problem's stated space complexity.

Alternative: Iterative BFS

You can also solve this with level-order traversal using a queue:

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    int depth = 0;
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        depth++;
    }
    return depth;
}

This runs in O(n) time and O(w) space where w is the maximum tree width. For a complete binary tree, the last level has n/2 nodes, so BFS can actually use more memory than the recursive DFS approach on balanced trees. In interviews, the recursive solution is typically expected first because it's cleaner and maps more directly to the tree's recursive definition.

Common Pitfalls

1. Forgetting the base case: Without if (root == null) return 0, you'll get a NullPointerException on the first leaf node's children.

2. Off-by-one error: Some candidates return max(left, right) without adding 1, forgetting to count the current node. Others return 1 for the base case instead of 0, which overcounts by 1 at every leaf.

3. Confusing depth with number of edges: Some definitions count edges instead of nodes. Our problem counts nodes. If the interviewer says "maximum depth of [3, 9, 20, #, #, 15, 7] is 2," they're counting edges. Clarify before coding.

4. Attempting an iterative DFS without a stack: If you try to avoid recursion, you need an explicit stack. Forgetting to push both children or losing track of the current depth are common bugs.

Interview Tips

When you encounter this problem in an interview:

1. Clarify definitions: "Should I count nodes or edges for the depth?" This shows attention to detail.

2. Start with the recursive approach: Trees are inherently recursive. The recursive solution is 5 lines, easy to explain, and easy to verify.

3. Trace through a small example: Draw the tree [1, 2, 3] and walk through the recursion. This catches off-by-one errors before your interviewer does.

4. Mention the iterative alternative: After presenting the recursive solution, briefly mention BFS as an alternative. This shows breadth of knowledge without overcomplicating your primary answer.

5. Anticipate follow-ups:

   • "What if we need the minimum depth instead?" (Similar recursion, but handle the one-child case carefully)
   • "How would you check if the tree is balanced?" (Compare left and right depths at every node)
   • "What about the diameter of the tree?" (Track the sum of left and right depths at each node)

Key Takeaways

• The recursive formula max(leftDepth, rightDepth) + 1 with a base case of 0 for null nodes is the standard approach for max depth in 2026 interviews.
• Time complexity is O(n) because every node is visited. Space complexity depends on tree shape: O(log n) for balanced, O(n) for skewed.
• This "solve children, combine results" pattern is the foundation for tree problems like balance checking, diameter, path sums, and subtree validation.
• The recursive DFS solution is preferred over iterative BFS for this problem because it's shorter, cleaner, and matches the tree's recursive structure.
• Always clarify with your interviewer whether depth counts nodes or edges. This problem counts nodes, where a single-node tree has depth 1.

Solutions in Other Languages

Python

class Solution:
    def max_depth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        left_depth = self.max_depth(root.left)
        right_depth = self.max_depth(root.right)
        return max(left_depth, right_depth) + 1

JavaScript

class Solution {
  maxDepth(root) {
    if (root === null) {
      return 0;
    }
    const leftDepth = this.maxDepth(root.left);
    const rightDepth = this.maxDepth(root.right);
    return Math.max(leftDepth, rightDepth) + 1;
  }
}

C++

class Solution {
public:
  int maxDepth(TreeNode *root) {
    if (root == nullptr) {
      return 0;
    }
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return std::max(leftDepth, rightDepth) + 1;
  }
};

Go

func (s *Solution) MaxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    leftDepth := s.MaxDepth(root.Left)
    rightDepth := s.MaxDepth(root.Right)
    return max(leftDepth, rightDepth) + 1
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

TypeScript

class Solution {
  maxDepth(root: TreeNode | null): number {
    if (root === null) {
      return 0;
    }
    const leftDepth = this.maxDepth(root.left);
    const rightDepth = this.maxDepth(root.right);
    return Math.max(leftDepth, rightDepth) + 1;
  }
}

Kotlin

class Solution {
  fun maxDepth(root: TreeNode?): Int {
    if (root == null) {
      return 0
    }
    val leftDepth = maxDepth(root.left)
    val rightDepth = maxDepth(root.right)
    return maxOf(leftDepth, rightDepth) + 1
  }
}

Scala

class Solution {
  def maxDepth(root: TreeNode): Int = {
    if (root == null) {
      0
    } else {
      val leftDepth = maxDepth(root.left)
      val rightDepth = maxDepth(root.right)
      Math.max(leftDepth, rightDepth) + 1
    }
  }
}

Swift

class Solution {
    func maxDepth(_ root: TreeNode?) -> Int {
        if root == nil {
            return 0
        }
        let leftDepth = maxDepth(root!.left)
        let rightDepth = maxDepth(root!.right)
        return max(leftDepth, rightDepth) + 1
    }
}

Ruby

class Solution
  def max_depth(root)
    return 0 if root.nil?
    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)
    [left_depth, right_depth].max + 1
  end
end

Rust

impl Solution {
    pub fn max_depth(&self, root: Option<Box<TreeNode>>) -> i32 {
        Self::depth(&root)
    }

    fn depth(node: &Option<Box<TreeNode>>) -> i32 {
        let node = match node {
            Some(n) => n,
            None => return 0,
        };
        let left_depth = Self::depth(&node.left);
        let right_depth = Self::depth(&node.right);
        std::cmp::max(left_depth, right_depth) + 1
    }
}

The Rust version uses a helper function that takes a reference to avoid ownership issues. The match on Option serves as the null check.

C#

public class Solution {
    public int MaxDepth(TreeNode? root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = MaxDepth(root.left);
        int rightDepth = MaxDepth(root.right);
        return Math.Max(leftDepth, rightDepth) + 1;
    }
}

Dart

class Solution {
  int maxDepth(TreeNode? root) {
    if (root == null) {
      return 0;
    }
    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);
    return max(leftDepth, rightDepth) + 1;
  }
}

PHP

class Solution {
    public function maxDepth(?TreeNode $root): int {
        if ($root === null) {
            return 0;
        }
        $leftDepth = $this->maxDepth($root->left);
        $rightDepth = $this->maxDepth($root->right);
        return max($leftDepth, $rightDepth) + 1;
    }
}

Related Problems

Once you're comfortable with max depth, these problems build on the same recursive pattern:

• Height of a Binary Tree - Virtually identical, reinforces the same recursion
• Check if a Binary Tree is Balanced - Uses max depth at every node to verify the height property
• Diameter of a Binary Tree - Tracks the sum of left and right depths instead of the max

Consistent practice with tree recursion is one of the most effective ways to prepare for coding interviews. This problem and hundreds of others are available on Firecode, where over 50,000 developers have built the skills to land offers at top tech companies. Whether you're just getting started with trees or preparing for your next on-site at Bloomberg or Amazon, drilling these fundamentals will pay off.

Happy coding, and may your trees never be too skewed! 🌲