Maximum Depth of Binary Tree

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 node down to the farthest leaf node.

What to notice first

• The depth is the count of nodes on the path, not the count of edges.
• An empty tree has depth 0, a single node has depth 1.
• Both DFS (recursive) and BFS (level-order) visit all nodes — the difference is memory and when you get the answer.

Examples

Input	Output	Explanation
[3,9,20,null,null,15,7]	3	Tree has height 3: root → 9, root → 20 → 15/7
[1,null,2]	2	Unbalanced tree: root → right child
[]	0	Empty tree

Visualized Examples

Example 1:       3          Depth: 3
              /     \
             9      20
                  /    \
                 15     7

Example 2:       1          Depth: 2
                  \
                   2

Example 3:    (empty)        Depth: 0

Constraints

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

Real-World Applications

Where this pattern appears

• Parse tree depth in compilers — determine how deeply nested expressions or statements are to verify they don’t exceed recursion limits.
• Directory structure analysis — find the deepest folder nesting in a file system.
• DOM tree inspection — measure how deeply nested HTML elements are for performance analysis.
• Organizational hierarchies — find the longest chain from CEO to individual contributors.
• Graph algorithms — establish bounds for recursion limits before traversing unknown tree structures.

Complexity Comparison

Approach	Time	Space	Best When
DFS Recursive	O(n)	O(h)	Small to medium trees; simple code preferred
BFS Level-Order	O(n)	O(w)	Early termination possible; breadth matters

Where h = height (at most n), w = max width (at most n)

Which approach should you learn first?

• Pick DFS Recursive if you want the simplest, most elegant solution. It’s the natural way to think about the problem.
• Pick BFS Level-Order if you want to understand tree level-by-level traversal or need to optimize for specific tree shapes.

Simplest

DFS Recursive

O(n) time · O(h) space

Level-by-Level

BFS Level-Order

O(n) time · O(w) space

Approach 1: DFS Recursive (Recommended)

★ Recommended

For each node, recursively find the maximum depth of its left and right subtrees, then return 1 plus the maximum of those two depths.

The insight is simple: the depth of a tree is 1 plus the depth of its taller subtree. For a null node, the depth is 0.

⏱ Time O(n) Visit all nodes once 💾 Space O(h) Recursion call stack

Step-by-step Example

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

       3
      / \
     9  20
       /  \
      15   7

Node	Left Subtree Depth	Right Subtree Depth	Result
15	0	0	1 + max(0, 0) = 1
7	0	0	1 + max(0, 0) = 1
9	0	0	1 + max(0, 0) = 1
20	1	1	1 + max(1, 1) = 2
3	1	2	1 + max(1, 2) = 3 ✓

Animated walkthrough

How DFS recursion finds the maximum depth

Use Next or Autoplay to watch as the recursion explores left subtree, right subtree, then combines results at each node.

Back Autoplay Next Reset

Step 1 of 5

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function maxDepthDFS(root):
    if root is null:
        return 0

    leftDepth = maxDepthDFS(root.left)
    rightDepth = maxDepthDFS(root.right)

    return 1 + max(leftDepth, rightDepth)

Solution Code

Python

maximum_depth_of_binary_tree_dfs.py

from typing import Optional


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


def maxDepth(root: Optional[TreeNode]) -> int:
    """
    Find the maximum depth of a binary tree using DFS (recursive).

    Time Complexity: O(n) where n is the number of nodes
    Space Complexity: O(h) where h is the height (call stack depth)
    """
    if root is None:
        return 0

    return 1 + max(maxDepth(root.left), maxDepth(root.right))


# Test cases
if __name__ == "__main__":
    # Example 1: [3,9,20,null,null,15,7]
    #       3
    #      / \
    #     9  20
    #       /  \
    #      15   7
    root1 = TreeNode(3)
    root1.left = TreeNode(9)
    root1.right = TreeNode(20)
    root1.right.left = TreeNode(15)
    root1.right.right = TreeNode(7)

    print(maxDepth(root1))  # Expected: 3

    # Example 2: [1,null,2]
    #     1
    #      \
    #       2
    root2 = TreeNode(1)
    root2.right = TreeNode(2)

    print(maxDepth(root2))  # Expected: 2

    # Example 3: Empty tree
    root3 = None
    print(maxDepth(root3))  # Expected: 0

C++

maximum_depth_of_binary_tree_dfs.cpp

#include <algorithm>
#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x = 0, TreeNode* l = nullptr, TreeNode* r = nullptr)
        : val(x), left(l), right(r) {}
};

int maxDepth(TreeNode* root) {
    /*
     * Find the maximum depth of a binary tree using DFS (recursive).
     *
     * Time Complexity: O(n) where n is the number of nodes
     * Space Complexity: O(h) where h is the height (call stack depth)
     */
    if (root == nullptr) {
        return 0;
    }

    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

// Test cases
int main() {
    // Example 1: [3,9,20,null,null,15,7]
    //       3
    //      / \
    //     9  20
    //       /  \
    //      15   7
    TreeNode* root1 = new TreeNode(3);
    root1->left = new TreeNode(9);
    root1->right = new TreeNode(20);
    root1->right->left = new TreeNode(15);
    root1->right->right = new TreeNode(7);

    cout << maxDepth(root1) << endl;  // Expected: 3

    // Example 2: [1,null,2]
    //     1
    //      \
    //       2
    TreeNode* root2 = new TreeNode(1);
    root2->right = new TreeNode(2);

    cout << maxDepth(root2) << endl;  // Expected: 2

    // Example 3: Empty tree
    TreeNode* root3 = nullptr;
    cout << maxDepth(root3) << endl;  // Expected: 0

    return 0;
}

Java

maximum_depth_of_binary_tree_dfs.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;
    }
}

public class maximum_depth_of_binary_tree_dfs {
    /*
     * Find the maximum depth of a binary tree using DFS (recursive).
     *
     * Time Complexity: O(n) where n is the number of nodes
     * Space Complexity: O(h) where h is the height (call stack depth)
     */
    public static int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }

    // Test cases
    public static void main(String[] args) {
        // Example 1: [3,9,20,null,null,15,7]
        //       3
        //      / \
        //     9  20
        //       /  \
        //      15   7
        TreeNode root1 = new TreeNode(3);
        root1.left = new TreeNode(9);
        root1.right = new TreeNode(20);
        root1.right.left = new TreeNode(15);
        root1.right.right = new TreeNode(7);

        System.out.println(maxDepth(root1)); // Expected: 3

        // Example 2: [1,null,2]
        //     1
        //      \
        //       2
        TreeNode root2 = new TreeNode(1);
        root2.right = new TreeNode(2);

        System.out.println(maxDepth(root2)); // Expected: 2

        // Example 3: Empty tree
        TreeNode root3 = null;
        System.out.println(maxDepth(root3)); // Expected: 0
    }
}

JavaScript

maximum_depth_of_binary_tree_dfs.js

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

/**
 * Find the maximum depth of a binary tree using DFS (recursive).
 *
 * Time Complexity: O(n) where n is the number of nodes
 * Space Complexity: O(h) where h is the height (call stack depth)
 *
 * @param {TreeNode} root
 * @return {number}
 */
function maxDepth(root) {
    if (root === null) {
        return 0;
    }

    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

// Example 1: [3,9,20,null,null,15,7]
//       3
//      / \
//     9  20
//       /  \
//      15   7
const root1 = new TreeNode(3);
root1.left = new TreeNode(9);
root1.right = new TreeNode(20);
root1.right.left = new TreeNode(15);
root1.right.right = new TreeNode(7);

console.log(maxDepth(root1)); // Expected: 3

// Example 2: [1,null,2]
//     1
//      \
//       2
const root2 = new TreeNode(1);
root2.right = new TreeNode(2);

console.log(maxDepth(root2)); // Expected: 2

// Example 3: Empty tree
const root3 = null;
console.log(maxDepth(root3)); // Expected: 0

export default maxDepth;

Rust

maximum_depth_of_binary_tree_dfs.rs

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

/*
 * Find the maximum depth of a binary tree using DFS (recursive).
 *
 * Time Complexity: O(n) where n is the number of nodes
 * Space Complexity: O(h) where h is the height (call stack depth)
 */
pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    match root {
        None => 0,
        Some(node) => {
            let node_ref = node.borrow();
            let left_depth = max_depth(node_ref.left.clone());
            let right_depth = max_depth(node_ref.right.clone());
            1 + left_depth.max(right_depth)
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_example1() {
        // [3,9,20,null,null,15,7]
        //       3
        //      / \
        //     9  20
        //       /  \
        //      15   7
        let mut root = TreeNode::new(3);
        root.left = Some(Rc::new(RefCell::new(TreeNode::new(9))));
        root.right = Some(Rc::new(RefCell::new(TreeNode::new(20))));

        if let Some(ref right) = root.right {
            let mut right_ref = right.borrow_mut();
            right_ref.left = Some(Rc::new(RefCell::new(TreeNode::new(15))));
            right_ref.right = Some(Rc::new(RefCell::new(TreeNode::new(7))));
        }

        assert_eq!(max_depth(Some(Rc::new(RefCell::new(root)))), 3);
    }

    #[test]
    fn test_example2() {
        // [1,null,2]
        //     1
        //      \
        //       2
        let mut root = TreeNode::new(1);
        root.right = Some(Rc::new(RefCell::new(TreeNode::new(2))));

        assert_eq!(max_depth(Some(Rc::new(RefCell::new(root)))), 2);
    }

    #[test]
    fn test_empty_tree() {
        assert_eq!(max_depth(None), 0);
    }
}

Go

maximum_depth_of_binary_tree_dfs.go

package main

/*
 * Find the maximum depth of a binary tree using DFS (recursive).
 *
 * Time Complexity: O(n) where n is the number of nodes
 * Space Complexity: O(h) where h is the height (call stack depth)
 */

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

func maxDepth(root *TreeNode) int {
  if root == nil {
    return 0
  }

  leftDepth := maxDepth(root.Left)
  rightDepth := maxDepth(root.Right)

  if leftDepth > rightDepth {
    return 1 + leftDepth
  }
  return 1 + rightDepth
}

// Test cases
func main() {
  // Example 1: [3,9,20,null,null,15,7]
  //       3
  //      / \
  //     9  20
  //       /  \
  //      15   7
  root1 := &TreeNode{Val: 3}
  root1.Left = &TreeNode{Val: 9}
  root1.Right = &TreeNode{Val: 20}
  root1.Right.Left = &TreeNode{Val: 15}
  root1.Right.Right = &TreeNode{Val: 7}

  println(maxDepth(root1)) // Expected: 3

  // Example 2: [1,null,2]
  //     1
  //      \
  //       2
  root2 := &TreeNode{Val: 1}
  root2.Right = &TreeNode{Val: 2}

  println(maxDepth(root2)) // Expected: 2

  // Example 3: Empty tree
  var root3 *TreeNode = nil
  println(maxDepth(root3)) // Expected: 0
}

Approach 2: BFS Level-Order Traversal

🎯 Interview Favourite

Use a queue to traverse the tree level by level. Increment the depth counter after processing each complete level. Return the depth when the queue becomes empty.

This approach processes nodes layer by layer, which can be more intuitive for understanding tree structure and is useful when you need information about each level.

⏱ Time O(n) Visit all nodes once 💾 Space O(w) Queue width at widest level

Step-by-step Example

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

       3           Level 1: process [3], depth = 1
      / \
     9  20         Level 2: process [9, 20], depth = 2
       /  \
      15   7       Level 3: process [15, 7], depth = 3

Step	Current Level	Queue After	Depth
1	[3]	[9, 20]	1
2	[9, 20]	[15, 7]	2
3	[15, 7]	[]	3
4	Queue empty	—	Return 3 ✓

Pseudocode

function maxDepthBFS(root):
    if root is null:
        return 0

    queue = [root]
    depth = 0

    while queue is not empty:
        depth += 1
        levelSize = length of queue

        for i = 0 to levelSize - 1:
            node = queue.dequeue()
            if node.left exists:
                queue.enqueue(node.left)
            if node.right exists:
                queue.enqueue(node.right)

    return depth

Solution Code

Python

maximum_depth_of_binary_tree_bfs.py

from typing import Optional
from collections import deque


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


def maxDepth(root: Optional[TreeNode]) -> int:
    """
    Find the maximum depth of a binary tree using BFS (level-order traversal).

    Time Complexity: O(n) where n is the number of nodes
    Space Complexity: O(w) where w is the maximum width of the tree
    """
    if root is None:
        return 0

    queue = deque([root])
    depth = 0

    while queue:
        depth += 1
        # Process all nodes at the current level
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return depth


# Test cases
if __name__ == "__main__":
    # Example 1: [3,9,20,null,null,15,7]
    #       3
    #      / \
    #     9  20
    #       /  \
    #      15   7
    root1 = TreeNode(3)
    root1.left = TreeNode(9)
    root1.right = TreeNode(20)
    root1.right.left = TreeNode(15)
    root1.right.right = TreeNode(7)

    print(maxDepth(root1))  # Expected: 3

    # Example 2: [1,null,2]
    #     1
    #      \
    #       2
    root2 = TreeNode(1)
    root2.right = TreeNode(2)

    print(maxDepth(root2))  # Expected: 2

    # Example 3: Empty tree
    root3 = None
    print(maxDepth(root3))  # Expected: 0

C++

maximum_depth_of_binary_tree_bfs.cpp

#include <iostream>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x = 0, TreeNode* l = nullptr, TreeNode* r = nullptr)
        : val(x), left(l), right(r) {}
};

int maxDepth(TreeNode* root) {
    /*
     * Find the maximum depth of a binary tree using BFS (level-order traversal).
     *
     * Time Complexity: O(n) where n is the number of nodes
     * Space Complexity: O(w) where w is the maximum width of the tree
     */
    if (root == nullptr) {
        return 0;
    }

    queue<TreeNode*> q;
    q.push(root);
    int depth = 0;

    while (!q.empty()) {
        depth++;
        // Process all nodes at the current level
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front();
            q.pop();
            if (node->left) {
                q.push(node->left);
            }
            if (node->right) {
                q.push(node->right);
            }
        }
    }

    return depth;
}

// Test cases
int main() {
    // Example 1: [3,9,20,null,null,15,7]
    //       3
    //      / \
    //     9  20
    //       /  \
    //      15   7
    TreeNode* root1 = new TreeNode(3);
    root1->left = new TreeNode(9);
    root1->right = new TreeNode(20);
    root1->right->left = new TreeNode(15);
    root1->right->right = new TreeNode(7);

    cout << maxDepth(root1) << endl;  // Expected: 3

    // Example 2: [1,null,2]
    //     1
    //      \
    //       2
    TreeNode* root2 = new TreeNode(1);
    root2->right = new TreeNode(2);

    cout << maxDepth(root2) << endl;  // Expected: 2

    // Example 3: Empty tree
    TreeNode* root3 = nullptr;
    cout << maxDepth(root3) << endl;  // Expected: 0

    return 0;
}

Java

maximum_depth_of_binary_tree_bfs.java

import java.util.*;

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;
    }
}

public class maximum_depth_of_binary_tree_bfs {
    /*
     * Find the maximum depth of a binary tree using BFS (level-order traversal).
     *
     * Time Complexity: O(n) where n is the number of nodes
     * Space Complexity: O(w) where w is the maximum width of the tree
     */
    public static int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;

        while (!queue.isEmpty()) {
            depth++;
            // Process all nodes at the current level
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }

        return depth;
    }

    // Test cases
    public static void main(String[] args) {
        // Example 1: [3,9,20,null,null,15,7]
        //       3
        //      / \
        //     9  20
        //       /  \
        //      15   7
        TreeNode root1 = new TreeNode(3);
        root1.left = new TreeNode(9);
        root1.right = new TreeNode(20);
        root1.right.left = new TreeNode(15);
        root1.right.right = new TreeNode(7);

        System.out.println(maxDepth(root1)); // Expected: 3

        // Example 2: [1,null,2]
        //     1
        //      \
        //       2
        TreeNode root2 = new TreeNode(1);
        root2.right = new TreeNode(2);

        System.out.println(maxDepth(root2)); // Expected: 2

        // Example 3: Empty tree
        TreeNode root3 = null;
        System.out.println(maxDepth(root3)); // Expected: 0
    }
}

JavaScript

maximum_depth_of_binary_tree_bfs.js

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

/**
 * Find the maximum depth of a binary tree using BFS (level-order traversal).
 *
 * Time Complexity: O(n) where n is the number of nodes
 * Space Complexity: O(w) where w is the maximum width of the tree
 *
 * @param {TreeNode} root
 * @return {number}
 */
function maxDepth(root) {
    if (root === null) {
        return 0;
    }

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

    while (queue.length > 0) {
        depth++;
        // Process all nodes at the current level
        const levelSize = queue.length;
        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;
}

// Example 1: [3,9,20,null,null,15,7]
//       3
//      / \
//     9  20
//       /  \
//      15   7
const root1 = new TreeNode(3);
root1.left = new TreeNode(9);
root1.right = new TreeNode(20);
root1.right.left = new TreeNode(15);
root1.right.right = new TreeNode(7);

console.log(maxDepth(root1)); // Expected: 3

// Example 2: [1,null,2]
//     1
//      \
//       2
const root2 = new TreeNode(1);
root2.right = new TreeNode(2);

console.log(maxDepth(root2)); // Expected: 2

// Example 3: Empty tree
const root3 = null;
console.log(maxDepth(root3)); // Expected: 0

export default maxDepth;

Rust

maximum_depth_of_binary_tree_bfs.rs

use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

/*
 * Find the maximum depth of a binary tree using BFS (level-order traversal).
 *
 * Time Complexity: O(n) where n is the number of nodes
 * Space Complexity: O(w) where w is the maximum width of the tree
 */
pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    match root {
        None => 0,
        Some(node) => {
            let mut queue = VecDeque::new();
            queue.push_back(node);
            let mut depth = 0;

            while !queue.is_empty() {
                depth += 1;
                let level_size = queue.len();

                for _ in 0..level_size {
                    if let Some(current) = queue.pop_front() {
                        let current_ref = current.borrow();
                        if let Some(left) = current_ref.left.clone() {
                            queue.push_back(left);
                        }
                        if let Some(right) = current_ref.right.clone() {
                            queue.push_back(right);
                        }
                    }
                }
            }

            depth
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_example1() {
        // [3,9,20,null,null,15,7]
        //       3
        //      / \
        //     9  20
        //       /  \
        //      15   7
        let mut root = TreeNode::new(3);
        root.left = Some(Rc::new(RefCell::new(TreeNode::new(9))));
        root.right = Some(Rc::new(RefCell::new(TreeNode::new(20))));

        if let Some(ref right) = root.right {
            let mut right_ref = right.borrow_mut();
            right_ref.left = Some(Rc::new(RefCell::new(TreeNode::new(15))));
            right_ref.right = Some(Rc::new(RefCell::new(TreeNode::new(7))));
        }

        assert_eq!(max_depth(Some(Rc::new(RefCell::new(root)))), 3);
    }

    #[test]
    fn test_example2() {
        // [1,null,2]
        //     1
        //      \
        //       2
        let mut root = TreeNode::new(1);
        root.right = Some(Rc::new(RefCell::new(TreeNode::new(2))));

        assert_eq!(max_depth(Some(Rc::new(RefCell::new(root)))), 2);
    }

    #[test]
    fn test_empty_tree() {
        assert_eq!(max_depth(None), 0);
    }
}

Go

maximum_depth_of_binary_tree_bfs.go

package main

/*
 * Find the maximum depth of a binary tree using BFS (level-order traversal).
 *
 * Time Complexity: O(n) where n is the number of nodes
 * Space Complexity: O(w) where w is the maximum width of the tree
 */

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

func maxDepth(root *TreeNode) int {
  if root == nil {
    return 0
  }

  queue := []*TreeNode{root}
  depth := 0

  for len(queue) > 0 {
    depth++
    // Process all nodes at the current level
    levelSize := len(queue)
    nextQueue := []*TreeNode{}

    for i := 0; i < levelSize; i++ {
      node := queue[i]
      if node.Left != nil {
        nextQueue = append(nextQueue, node.Left)
      }
      if node.Right != nil {
        nextQueue = append(nextQueue, node.Right)
      }
    }

    queue = nextQueue
  }

  return depth
}

// Test cases
func main() {
  // Example 1: [3,9,20,null,null,15,7]
  //       3
  //      / \
  //     9  20
  //       /  \
  //      15   7
  root1 := &TreeNode{Val: 3}
  root1.Left = &TreeNode{Val: 9}
  root1.Right = &TreeNode{Val: 20}
  root1.Right.Left = &TreeNode{Val: 15}
  root1.Right.Right = &TreeNode{Val: 7}

  println(maxDepth(root1)) // Expected: 3

  // Example 2: [1,null,2]
  //     1
  //      \
  //       2
  root2 := &TreeNode{Val: 1}
  root2.Right = &TreeNode{Val: 2}

  println(maxDepth(root2)) // Expected: 2

  // Example 3: Empty tree
  var root3 *TreeNode = nil
  println(maxDepth(root3)) // Expected: 0
}

Related Problems

• Minimum Depth of Binary Tree ↗ Easy #111
• Binary Tree Zigzag Level Order Traversal ↗ Medium #103
• Binary Tree Level Order Traversal ↗ Medium #102
• Same Tree ↗ Easy #100

Interview Tips

Key trade-offs to discuss

• DFS vs BFS: Both are O(n), but DFS uses call stack (implicit) while BFS uses explicit queue. DFS is typically simpler to code; BFS is easier to parallelize.
• Memory for skewed trees: A completely unbalanced tree (like a linked list) uses O(n) space in DFS (deep recursion) but O(1) in BFS (only queue has one node at a time).
• When to use BFS: If you need the minimum depth (can stop early when reaching a leaf) or if you need per-level processing.
• Follow-ups to expect: minimum depth, level-order traversal, validate balanced tree, find all leaves, or modifications like “sum at each level.”

← Previous
#103 Binary Tree Zigzag Level Order Traversal Next
#105 Construct Binary Tree from Preorder and Inorder Traversal →