Maximum Depth of Binary Tree

Problem Statement

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

Input:

• Root of a binary tree

Output:

• Integer representing the maximum depth

Constraints:

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

Examples:

Example 1:

    3
   / \
  9  20
    /  \
   15   7

Input: root = [3,9,20,null,null,15,7]
Output: 3
Explanation: Maximum depth is 3 (root -> 20 -> 15 or root -> 20 -> 7)

Example 2:

  1
   \
    2

Input: root = [1,null,2]
Output: 2

Example 3:

Input: root = []
Output: 0

Example 4:

Input: root = [0]
Output: 1

Solutions

Approach 1: Recursive DFS (Top-Down)

Use recursion to calculate the maximum depth by exploring both subtrees.

Algorithm:

1. Base case: if node is null, return 0
2. Recursively calculate depth of left and right subtrees
3. Return 1 + max(left_depth, right_depth)

Python:

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

def maxDepth(root):
    """
    Recursive approach to find maximum depth
    Time: O(N) where N is number of nodes
    Space: O(H) where H is height of tree (recursion stack)
    """
    if not root:
        return 0
    
    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)
    
    return 1 + max(left_depth, right_depth)

def maxDepthCompact(root):
    """
    More compact recursive solution
    Time: O(N)
    Space: O(H)
    """
    return 0 if not root else 1 + max(maxDepthCompact(root.left), maxDepthCompact(root.right))

def maxDepthWithPath(root):
    """
    Return both max depth and the path to deepest node
    Time: O(N)
    Space: O(H)
    """
    def dfs(node):
        if not node:
            return 0, []
        
        left_depth, left_path = dfs(node.left)
        right_depth, right_path = dfs(node.right)
        
        if left_depth > right_depth:
            return left_depth + 1, [node.val] + left_path
        else:
            return right_depth + 1, [node.val] + right_path
    
    depth, path = dfs(root)
    return depth, path

Java:

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 {
    /**
     * Recursive approach to find maximum depth
     * Time: O(N)
     * Space: O(H)
     */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        
        return 1 + Math.max(leftDepth, rightDepth);
    }
    
    /**
     * More compact recursive solution
     * Time: O(N)
     * Space: O(H)
     */
    public int maxDepthCompact(TreeNode root) {
        return root == null ? 0 : 1 + Math.max(maxDepthCompact(root.left), maxDepthCompact(root.right));
    }
    
    public class DepthResult {
        int depth;
        List<Integer> path;
        
        DepthResult(int depth, List<Integer> path) {
            this.depth = depth;
            this.path = path;
        }
    }
    
    /**
     * Return both max depth and path to deepest node
     * Time: O(N)
     * Space: O(H)
     */
    public DepthResult maxDepthWithPath(TreeNode root) {
        return dfs(root);
    }
    
    private DepthResult dfs(TreeNode node) {
        if (node == null) {
            return new DepthResult(0, new ArrayList<>());
        }
        
        DepthResult left = dfs(node.left);
        DepthResult right = dfs(node.right);
        
        if (left.depth > right.depth) {
            List<Integer> path = new ArrayList<>();
            path.add(node.val);
            path.addAll(left.path);
            return new DepthResult(left.depth + 1, path);
        } else {
            List<Integer> path = new ArrayList<>();
            path.add(node.val);
            path.addAll(right.path);
            return new DepthResult(right.depth + 1, path);
        }
    }
}

Go:

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// maxDepth - Recursive approach to find maximum depth
// Time: O(N)
// Space: O(H)
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    
    leftDepth := maxDepth(root.Left)
    rightDepth := maxDepth(root.Right)
    
    if leftDepth > rightDepth {
        return leftDepth + 1
    }
    return rightDepth + 1
}

// maxDepthCompact - More compact recursive solution
// Time: O(N)
// Space: O(H)
func maxDepthCompact(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return 1 + max(maxDepthCompact(root.Left), maxDepthCompact(root.Right))
}

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

type DepthResult struct {
    Depth int
    Path  []int
}

// maxDepthWithPath - Return both max depth and path to deepest node
// Time: O(N)
// Space: O(H)
func maxDepthWithPath(root *TreeNode) DepthResult {
    if root == nil {
        return DepthResult{0, []int{}}
    }
    
    left := maxDepthWithPath(root.Left)
    right := maxDepthWithPath(root.Right)
    
    if left.Depth > right.Depth {
        path := append([]int{root.Val}, left.Path...)
        return DepthResult{left.Depth + 1, path}
    } else {
        path := append([]int{root.Val}, right.Path...)
        return DepthResult{right.Depth + 1, path}
    }
}

JavaScript:

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

/**
 * Recursive approach to find maximum depth
 * Time: O(N)
 * Space: O(H)
 */
function maxDepth(root) {
    if (!root) {
        return 0;
    }
    
    const leftDepth = maxDepth(root.left);
    const rightDepth = maxDepth(root.right);
    
    return 1 + Math.max(leftDepth, rightDepth);
}

/**
 * More compact recursive solution
 * Time: O(N)
 * Space: O(H)
 */
function maxDepthCompact(root) {
    return !root ? 0 : 1 + Math.max(maxDepthCompact(root.left), maxDepthCompact(root.right));
}

/**
 * Return both max depth and path to deepest node
 * Time: O(N)
 * Space: O(H)
 */
function maxDepthWithPath(root) {
    function dfs(node) {
        if (!node) {
            return { depth: 0, path: [] };
        }
        
        const left = dfs(node.left);
        const right = dfs(node.right);
        
        if (left.depth > right.depth) {
            return { depth: left.depth + 1, path: [node.val, ...left.path] };
        } else {
            return { depth: right.depth + 1, path: [node.val, ...right.path] };
        }
    }
    
    return dfs(root);
}

C#:

using System;
using System.Collections.Generic;

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

public class Solution {
    /// <summary>
    /// Recursive approach to find maximum depth
    /// Time: O(N)
    /// Space: O(H)
    /// </summary>
    public int MaxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int leftDepth = MaxDepth(root.left);
        int rightDepth = MaxDepth(root.right);
        
        return 1 + Math.Max(leftDepth, rightDepth);
    }
    
    /// <summary>
    /// More compact recursive solution
    /// Time: O(N)
    /// Space: O(H)
    /// </summary>
    public int MaxDepthCompact(TreeNode root) {
        return root == null ? 0 : 1 + Math.Max(MaxDepthCompact(root.left), MaxDepthCompact(root.right));
    }
    
    public class DepthResult {
        public int Depth { get; set; }
        public List<int> Path { get; set; }
        
        public DepthResult(int depth, List<int> path) {
            Depth = depth;
            Path = path;
        }
    }
    
    /// <summary>
    /// Return both max depth and path to deepest node
    /// Time: O(N)
    /// Space: O(H)
    /// </summary>
    public DepthResult MaxDepthWithPath(TreeNode root) {
        return Dfs(root);
    }
    
    private DepthResult Dfs(TreeNode node) {
        if (node == null) {
            return new DepthResult(0, new List<int>());
        }
        
        var left = Dfs(node.left);
        var right = Dfs(node.right);
        
        if (left.Depth > right.Depth) {
            var path = new List<int> { node.val };
            path.AddRange(left.Path);
            return new DepthResult(left.Depth + 1, path);
        } else {
            var path = new List<int> { node.val };
            path.AddRange(right.Path);
            return new DepthResult(right.Depth + 1, path);
        }
    }
}

Approach 2: Iterative DFS using Stack

Use an explicit stack to simulate recursion with depth tracking.

Python:

def maxDepthIterativeDFS(root):
    """
    Iterative DFS using stack with depth tracking
    Time: O(N)
    Space: O(H)
    """
    if not root:
        return 0
    
    stack = [(root, 1)]  # (node, current_depth)
    max_depth = 0
    
    while stack:
        node, depth = stack.pop()
        max_depth = max(max_depth, depth)
        
        if node.right:
            stack.append((node.right, depth + 1))
        if node.left:
            stack.append((node.left, depth + 1))
    
    return max_depth

Java:

public int maxDepthIterativeDFS(TreeNode root) {
    /**
     * Iterative DFS using stack with depth tracking
     * Time: O(N)
     * Space: O(H)
     */
    if (root == null) {
        return 0;
    }
    
    Stack<Pair<TreeNode, Integer>> stack = new Stack<>();
    stack.push(new Pair<>(root, 1));
    int maxDepth = 0;
    
    while (!stack.isEmpty()) {
        Pair<TreeNode, Integer> current = stack.pop();
        TreeNode node = current.getKey();
        int depth = current.getValue();
        
        maxDepth = Math.max(maxDepth, depth);
        
        if (node.right != null) {
            stack.push(new Pair<>(node.right, depth + 1));
        }
        if (node.left != null) {
            stack.push(new Pair<>(node.left, depth + 1));
        }
    }
    
    return maxDepth;
}

class Pair<K, V> {
    private K key;
    private V value;
    
    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }
    
    public K getKey() { return key; }
    public V getValue() { return value; }
}

Go:

type NodeDepth struct {
    node  *TreeNode
    depth int
}

// maxDepthIterativeDFS - Iterative DFS using stack with depth tracking
// Time: O(N)
// Space: O(H)
func maxDepthIterativeDFS(root *TreeNode) int {
    if root == nil {
        return 0
    }
    
    stack := []NodeDepth{{root, 1}}
    maxDepth := 0
    
    for len(stack) > 0 {
        current := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        
        if current.depth > maxDepth {
            maxDepth = current.depth
        }
        
        if current.node.Right != nil {
            stack = append(stack, NodeDepth{current.node.Right, current.depth + 1})
        }
        if current.node.Left != nil {
            stack = append(stack, NodeDepth{current.node.Left, current.depth + 1})
        }
    }
    
    return maxDepth
}

JavaScript:

/**
 * Iterative DFS using stack with depth tracking
 * Time: O(N)
 * Space: O(H)
 */
function maxDepthIterativeDFS(root) {
    if (!root) {
        return 0;
    }
    
    const stack = [[root, 1]];  // [node, depth]
    let maxDepth = 0;
    
    while (stack.length > 0) {
        const [node, depth] = stack.pop();
        maxDepth = Math.max(maxDepth, depth);
        
        if (node.right) {
            stack.push([node.right, depth + 1]);
        }
        if (node.left) {
            stack.push([node.left, depth + 1]);
        }
    }
    
    return maxDepth;
}

C#:

public int MaxDepthIterativeDFS(TreeNode root) {
    /// <summary>
    /// Iterative DFS using stack with depth tracking
    /// Time: O(N)
    /// Space: O(H)
    /// </summary>
    if (root == null) {
        return 0;
    }
    
    Stack<(TreeNode node, int depth)> stack = new Stack<(TreeNode, int)>();
    stack.Push((root, 1));
    int maxDepth = 0;
    
    while (stack.Count > 0) {
        var (node, depth) = stack.Pop();
        maxDepth = Math.Max(maxDepth, depth);
        
        if (node.right != null) {
            stack.Push((node.right, depth + 1));
        }
        if (node.left != null) {
            stack.Push((node.left, depth + 1));
        }
    }
    
    return maxDepth;
}

Approach 3: BFS (Level-Order Traversal)

Use BFS to traverse level by level and count the number of levels.

Python:

from collections import deque

def maxDepthBFS(root):
    """
    BFS approach using queue
    Time: O(N)
    Space: O(W) where W is maximum width of tree
    """
    if not root:
        return 0
    
    queue = deque([root])
    depth = 0
    
    while queue:
        depth += 1
        level_size = len(queue)
        
        # Process all nodes at current level
        for _ in range(level_size):
            node = queue.popleft()
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return depth

def maxDepthBFSWithLevels(root):
    """
    BFS that also returns nodes at each level
    Time: O(N)
    Space: O(W)
    """
    if not root:
        return 0, []
    
    queue = deque([root])
    levels = []
    
    while queue:
        level_nodes = []
        level_size = len(queue)
        
        for _ in range(level_size):
            node = queue.popleft()
            level_nodes.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        levels.append(level_nodes)
    
    return len(levels), levels

Java:

public int maxDepthBFS(TreeNode root) {
    /**
     * BFS approach using queue
     * Time: O(N)
     * Space: O(W) where W is maximum width
     */
    if (root == null) {
        return 0;
    }
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int depth = 0;
    
    while (!queue.isEmpty()) {
        depth++;
        int levelSize = queue.size();
        
        // Process all nodes at current level
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
    
    return depth;
}

Go:

// maxDepthBFS - BFS approach using queue
// Time: O(N)
// Space: O(W) where W is maximum width
func maxDepthBFS(root *TreeNode) int {
    if root == nil {
        return 0
    }
    
    queue := []*TreeNode{root}
    depth := 0
    
    for len(queue) > 0 {
        depth++
        levelSize := len(queue)
        
        // Process all nodes at current level
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    
    return depth
}

JavaScript:

/**
 * BFS approach using queue
 * Time: O(N)
 * Space: O(W) where W is maximum width
 */
function maxDepthBFS(root) {
    if (!root) {
        return 0;
    }
    
    const queue = [root];
    let depth = 0;
    
    while (queue.length > 0) {
        depth++;
        const levelSize = queue.length;
        
        // Process all nodes at current level
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            
            if (node.left) {
                queue.push(node.left);
            }
            if (node.right) {
                queue.push(node.right);
            }
        }
    }
    
    return depth;
}

C#:

public int MaxDepthBFS(TreeNode root) {
    /// <summary>
    /// BFS approach using queue
    /// Time: O(N)
    /// Space: O(W) where W is maximum width
    /// </summary>
    if (root == null) {
        return 0;
    }
    
    Queue<TreeNode> queue = new Queue<TreeNode>();
    queue.Enqueue(root);
    int depth = 0;
    
    while (queue.Count > 0) {
        depth++;
        int levelSize = queue.Count;
        
        // Process all nodes at current level
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.Dequeue();
            
            if (node.left != null) {
                queue.Enqueue(node.left);
            }
            if (node.right != null) {
                queue.Enqueue(node.right);
            }
        }
    }
    
    return depth;
}

Key Insights

1. Height vs Depth: Maximum depth equals height of the tree
2. DFS vs BFS: DFS uses recursion/stack, BFS uses queue and processes level by level
3. Base Case: Empty tree has depth 0, single node has depth 1
4. Space Complexity: Recursive DFS is O(H), BFS is O(W) where W is max width

Edge Cases

1. Empty tree: Return 0
2. Single node: Return 1
3. Left skewed tree: Depth equals number of nodes
4. Right skewed tree: Depth equals number of nodes
5. Balanced tree: Depth is logarithmic in number of nodes

Common Mistakes

1. Off-by-one errors: Not properly counting the root level
2. Base case handling: Not handling null nodes correctly
3. Stack overflow: Deep recursion on skewed trees
4. BFS level counting: Not properly tracking level boundaries

Follow-up Questions

1. Minimum depth: Find the minimum depth to a leaf node
2. Diameter: Find the longest path between any two nodes
3. Balanced check: Determine if tree is height-balanced
4. Path to deepest: Return the path from root to deepest leaf
5. All deepest nodes: Find all nodes at maximum depth