104. Maximum Depth of Binary Tree - Explanation

Description

Given the root of a binary tree, return its depth.

The depth of a binary tree is defined as the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

Input: root = [1,2,3,null,null,4]

Output: 3

Example 2:

Input: root = []

Output: 0

Constraints:

0 <= The number of nodes in the tree <= 100.
-100 <= Node.val <= 100

Topics

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(n) space, where n is the number of nodes in the tree.

Hint 1

From the definition of binary tree's maximum depth, Can you think of a way to achieve this recursively? Maybe you should consider the max depth of the subtrees first before computing the maxdepth at the root.

Hint 2

We use the Depth First Search (DFS) algorithm to find the maximum depth of a binary tree, starting from the root. For the subtrees rooted at the left and right children of the root node, we calculate their maximum depths recursively going through left and right subtrees. We return 1 + max(leftDepth, rightDepth). Why?

Hint 3

The +1 accounts for the current node, as it contributes to the current depth in the recursion call. We pass the maximum depth from the current node's left and right subtrees to its parent because the current maximum depth determines the longest path from the parent to a leaf node through this subtree.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Binary Trees - Understanding tree node structure with left/right children
Recursion - Writing functions that call themselves with smaller subproblems
Depth-First Search (DFS) - Traversing trees by exploring as deep as possible before backtracking
Breadth-First Search (BFS) - Traversing trees level by level using a queue

1. Recursive DFS

Intuition

Recursive DFS computes the maximum depth of a binary tree by exploring every node.
The idea is simple:

The depth of a tree = 1 + maximum depth of its left and right subtrees.
If a node is None, its depth is 0.

So for each node:

Recursively compute the depth of the left subtree.
Recursively compute the depth of the right subtree.
Take the maximum of the two.
Add 1 for the current node.

Algorithm

If root is null, return 0.
Otherwise:
- Recursively compute leftDepth = maxDepth(root.left).
- Recursively compute rightDepth = maxDepth(root.right).
Return 1 + max(leftDepth, rightDepth).

# 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 not root:
            return 0

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

/**
 * Definition for a binary tree node.
 * public 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 Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }

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

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    /**
     * @param {TreeNode} root
     * @return {number}
     */
    maxDepth(root) {
        if (root === null) {
            return 0;
        }

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

/**
 * Definition for a binary tree node.
 * 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 {
    public int MaxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return 1 + Math.Max(MaxDepth(root.left), MaxDepth(root.right));
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return 1 + max(maxDepth(root.Left), maxDepth(root.Right))
}

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

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun maxDepth(root: TreeNode?): Int {
        if (root == null) {
            return 0
        }
        return 1 + maxOf(maxDepth(root.left), maxDepth(root.right))
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func maxDepth(_ root: TreeNode?) -> Int {
        guard let root = root else { return 0 }
        return 1 + max(maxDepth(root.left), maxDepth(root.right))
    }
}

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }

impl Solution {
    pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        match root {
            None => 0,
            Some(node) => {
                let node = node.borrow();
                1 + std::cmp::max(
                    Self::max_depth(node.left.clone()),
                    Self::max_depth(node.right.clone()),
                )
            }
        }
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(h)$ $O (h)$
- Best Case (balanced tree): $O(log(n))$
- Worst Case (degenerate tree): $O(n)$

Where $n$ is the number of nodes in the tree and $h$ is the height of the tree.

2. Iterative DFS (Stack)

Intuition

Instead of relying on recursion to explore the tree, we can simulate DFS explicitly using a stack.
The stack will store pairs of:

the current node
the depth of that node in the tree

Every time we pop a node from the stack:

We update the maximum depth seen so far.
We push its left and right children onto the stack with depth + 1.

This approach works like a manual DFS where we keep track of depth ourselves.
It avoids recursion and is useful when recursion depth may become too large.

Algorithm

If the root is null, return 0.
Initialize a stack with the pair (root, 1) to represent depth 1.
Initialize maxDepth = 0.
While the stack is not empty:
- Pop (node, depth).
- Update maxDepth = max(maxDepth, depth).
- Push (node.left, depth + 1) onto the stack if left child exists.
- Push (node.right, depth + 1) onto the stack if right child exists.
When the stack becomes empty, return maxDepth.

# 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:
        stack = [[root, 1]]
        res = 0

        while stack:
            node, depth = stack.pop()

            if node:
                res = max(res, depth)
                stack.append([node.left, depth + 1])
                stack.append([node.right, depth + 1])
        return res

/**
 * Definition for a binary tree node.
 * public 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 Solution {
    public int maxDepth(TreeNode root) {
        Stack<Pair<TreeNode, Integer>> stack = new Stack<>();
        stack.push(new Pair<>(root, 1));
        int res = 0;

        while (!stack.isEmpty()) {
            Pair<TreeNode, Integer> current = stack.pop();
            TreeNode node = current.getKey();
            int depth = current.getValue();

            if (node != null) {
                res = Math.max(res, depth);
                stack.push(new Pair<>(node.left, depth + 1));
                stack.push(new Pair<>(node.right, depth + 1));
            }
        }
        return res;
    }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    int maxDepth(TreeNode* root) {
        stack<pair<TreeNode*, int>> stack;
        stack.push({root, 1});
        int res = 0;

        while (!stack.empty()) {
            pair<TreeNode*, int> current = stack.top();
            stack.pop();
            TreeNode* node = current.first;
            int depth = current.second;

            if (node != nullptr) {
                res = max(res, depth);
                stack.push({node->left, depth + 1});
                stack.push({node->right, depth + 1});
            }
        }
        return res;
    }
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    /**
     * @param {TreeNode} root
     * @return {number}
     */
    maxDepth(root) {
        const stack = [[root, 1]];
        let res = 0;

        while (stack.length > 0) {
            const current = stack.pop();
            const node = current[0];
            const depth = current[1];

            if (node !== null) {
                res = Math.max(res, depth);
                stack.push([node.left, depth + 1]);
                stack.push([node.right, depth + 1]);
            }
        }
        return res;
    }
}

/**
 * Definition for a binary tree node.
 * 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 {
    public int MaxDepth(TreeNode root) {
        Stack<Tuple<TreeNode, int>> stack = new Stack<Tuple<TreeNode, int>>();
        stack.Push(new Tuple<TreeNode, int>(root, 1));
        int res = 0;

        while (stack.Count > 0) {
            Tuple<TreeNode, int> current = stack.Pop();
            TreeNode node = current.Item1;
            int depth = current.Item2;

            if (node != null) {
                res = Math.Max(res, depth);
                stack.Push(new Tuple<TreeNode, int>(node.left, depth + 1));
                stack.Push(new Tuple<TreeNode, int>(node.right, depth + 1));
            }
        }
        return res;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }

    stack := list.New()
    stack.PushBack([]interface{}{root, 1})
    res := 0

    for stack.Len() > 0 {
        back := stack.Back()
        stack.Remove(back)
        pair := back.Value.([]interface{})
        node := pair[0].(*TreeNode)
        depth := pair[1].(int)

        if node != nil {
            res = max(res, depth)
            stack.PushBack([]interface{}{node.Left, depth + 1})
            stack.PushBack([]interface{}{node.Right, depth + 1})
        }
    }

    return res
}

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

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun maxDepth(root: TreeNode?): Int {
        if (root == null) {
            return 0
        }

        val stack = ArrayDeque<Pair<TreeNode?, Int>>()
        stack.addLast(Pair(root, 1))
        var res = 0

        while (stack.isNotEmpty()) {
            val (node, depth) = stack.removeLast()

            if (node != null) {
                res = maxOf(res, depth)
                stack.addLast(Pair(node.left, depth + 1))
                stack.addLast(Pair(node.right, depth + 1))
            }
        }

        return res
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func maxDepth(_ root: TreeNode?) -> Int {
        var stack: [(TreeNode?, Int)] = [(root, 1)]
        var res = 0

        while !stack.isEmpty {
            let (node, depth) = stack.removeLast()

            if let node = node {
                res = max(res, depth)
                stack.append((node.left, depth + 1))
                stack.append((node.right, depth + 1))
            }
        }
        return res
    }
}

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }

impl Solution {
    pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut stack: Vec<(Option<Rc<RefCell<TreeNode>>>, i32)> = vec![(root, 1)];
        let mut res = 0;

        while let Some((node, depth)) = stack.pop() {
            if let Some(n) = node {
                let n = n.borrow();
                res = res.max(depth);
                stack.push((n.left.clone(), depth + 1));
                stack.push((n.right.clone(), depth + 1));
            }
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Breadth First Search

Intuition

Breadth-First Search (BFS) processes the tree level by level.
This makes it a perfect fit for computing the maximum depth because:

Every iteration of BFS processes one entire level of the tree.
So each completed level corresponds to increasing the depth by 1.

We simply count how many levels we traverse until the queue becomes empty.

Think of the queue like a moving frontier:

Start with the root → depth = 1
Add its children → depth = 2
Add their children → depth = 3
Continue until no nodes remain.

The number of BFS layers processed is exactly the depth of the tree.

Algorithm

If the tree is empty (root == null), return 0.
Initialize a queue and push the root.
Initialize level = 0.
While the queue is not empty:
- Determine the number of nodes at the current level (size = len(queue)).
- Process all size nodes:
  - Pop from the queue.
  - Push their left and right children if they exist.
- After processing the entire level, increment level.
Return level when the queue becomes empty.

# 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:
        q = deque()
        if root:
            q.append(root)

        level = 0
        while q:
            for i in range(len(q)):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            level += 1
        return level

/**
 * Definition for a binary tree node.
 * public 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 Solution {
    public int maxDepth(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        if (root != null) {
            q.add(root);
        }

        int level = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                if (node.left != null) {
                    q.add(node.left);
                }
                if (node.right != null) {
                    q.add(node.right);
                }
            }
            level++;
        }
        return level;
    }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue<TreeNode*> q;
        if (root != nullptr) {
            q.push(root);
        }

        int level = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                if (node->left != nullptr) {
                    q.push(node->left);
                }
                if (node->right != nullptr) {
                    q.push(node->right);
                }
            }
            level++;
        }
        return level;
    }
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    /**
     * @param {TreeNode} root
     * @return {number}
     */
    maxDepth(root) {
        const q = new Queue();
        if (root !== null) {
            q.push(root);
        }

        let level = 0;
        while (q.size() > 0) {
            const size = q.size();
            for (let i = 0; i < size; i++) {
                const node = q.pop();
                if (node.left !== null) {
                    q.push(node.left);
                }
                if (node.right !== null) {
                    q.push(node.right);
                }
            }
            level++;
        }
        return level;
    }
}

/**
 * Definition for a binary tree node.
 * 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 {
    public int MaxDepth(TreeNode root) {
        Queue<TreeNode> q = new Queue<TreeNode>();
        if (root != null) {
            q.Enqueue(root);
        }

        int level = 0;
        while (q.Count > 0) {
            int size = q.Count;
            for (int i = 0; i < size; i++) {
                TreeNode node = q.Dequeue();
                if (node.left != null) {
                    q.Enqueue(node.left);
                }
                if (node.right != null) {
                    q.Enqueue(node.right);
                }
            }
            level++;
        }
        return level;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
   if root == nil {
       return 0
   }

   q := linkedlistqueue.New()
   q.Enqueue(root)
   level := 0

   for !q.Empty() {
       size := q.Size()

       for i := 0; i < size; i++ {
           val, _ := q.Dequeue()
           node := val.(*TreeNode)

           if node.Left != nil {
               q.Enqueue(node.Left)
           }
           if node.Right != nil {
               q.Enqueue(node.Right)
           }
       }
       level++
   }

   return level
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun maxDepth(root: TreeNode?): Int {
        if (root == null) {
            return 0
        }

        val q = ArrayDeque<TreeNode>()
        q.addLast(root)
        var level = 0

        while (q.isNotEmpty()) {
            val size = q.size

            repeat(size) {
                val node = q.removeFirst()

                node.left?.let { q.addLast(it) }
                node.right?.let { q.addLast(it) }
            }
            level++
        }

        return level
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func maxDepth(_ root: TreeNode?) -> Int {
        var queue = Deque<TreeNode>()
        if let root = root {
            queue.append(root)
        }

        var level = 0
        while !queue.isEmpty {
            for _ in 0..<queue.count {
                let node = queue.removeFirst()
                if let left = node.left {
                    queue.append(left)
                }
                if let right = node.right {
                    queue.append(right)
                }
            }
            level += 1
        }
        return level
    }
}

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }

impl Solution {
    pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut queue = VecDeque::new();
        if let Some(r) = root {
            queue.push_back(r);
        }

        let mut level = 0;
        while !queue.is_empty() {
            let size = queue.len();
            for _ in 0..size {
                let node = queue.pop_front().unwrap();
                let node = node.borrow();
                if let Some(ref left) = node.left {
                    queue.push_back(left.clone());
                }
                if let Some(ref right) = node.right {
                    queue.push_back(right.clone());
                }
            }
            level += 1;
        }
        level
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Common Pitfalls

Confusing Depth with Height

Depth is measured from the root down (root has depth 1 or 0 depending on convention), while height is measured from the leaves up. The maximum depth of a tree equals its height when counting from root. Be consistent with whether you start counting at 0 or 1.

# If root is None, depth is 0 (no nodes)
# If root exists with no children, depth is 1 (one node)
def maxDepth(self, root):
    if not root:
        return 0  # Base case: empty tree has depth 0
    return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

Forgetting to Handle the Empty Tree Case

An empty tree (null root) has a depth of 0. Failing to check for this base case before accessing node properties will cause a null pointer exception.

# Wrong: No null check
def maxDepth(self, root):
    return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
    # Crashes when root is None

# Correct: Handle empty tree first
def maxDepth(self, root):
    if not root:
        return 0
    return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))