Maximum Depth of Binary Tree

Easy

#0104Time: O(N)Space: O(H)15 companies

Algorithms

Depth-First Search Breadth-First Search

Data structures

Tree Binary Tree

Companies

Accenture Adobe Apple Bloomberg

Prompt

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.

Example 1:

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

Example 2:

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

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This is the most intuitive and common approach. It leverages the recursive nature of a tree. The maximum depth of a tree is defined as 1 (for the root) plus the maximum of the depths of its left and right subtrees.

Algorithm

If the root node is null, return 0.
Calculate the depth of the left subtree by making a recursive call: leftDepth = maxDepth(root.left).
Calculate the depth of the right subtree by making a recursive call: rightDepth = maxDepth(root.right).
Return 1 + max(leftDepth, rightDepth).

Walkthrough

The algorithm works by defining a function that calculates the depth of a subtree rooted at a given node.

Base Case: If the current node is null, it represents an empty tree or the end of a path, which has a depth of 0.
Recursive Step: For a non-null node, we recursively call the function on its left and right children to find the depths of the left and right subtrees (leftDepth and rightDepth).
The depth of the tree rooted at the current node is then 1 + Math.max(leftDepth, rightDepth). The +1 accounts for the current node itself. The process starts by calling this function with the root of the entire tree.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public int maxDepth(TreeNode root) {18        if (root == null) {19            return 0;20        }21        22        int leftDepth = maxDepth(root.left);23        int rightDepth = maxDepth(root.right);24        25        return Math.max(leftDepth, rightDepth) + 1;26    }27}

Complexity

Time

O(N)

Space

O(H)

Trade-offs

Pros

The code is very concise, elegant, and easy to understand.
It directly models the recursive definition of a tree's depth.

Cons

For extremely deep trees, it might lead to a StackOverflowError due to deep recursion.
Can be less space-efficient than BFS for very skewed trees where the height approaches the number of nodes.

This approach uses an iterative, level-by-level traversal (BFS) to find the depth. The maximum depth is simply the total number of levels traversed. This method avoids recursion and is often more robust against very deep trees.

Algorithm

Handle the edge case: if root is null, return 0.
Initialize a Queue and add the root to it.
Initialize a depth counter to 0.
Loop while the queue is not empty:
- Increment depth.
- Get the current level's size: levelSize = queue.size().
- Loop levelSize times:
  - Dequeue a node.
  - Enqueue its non-null left and right children.
Return depth.

Walkthrough

We use a queue to store nodes that need to be visited.

We start by adding the root to the queue. If the root is null, the depth is 0.
We then iterate level by level. A depth counter is incremented for each level.
In each iteration of the main loop, we process all nodes at the current level. We find the number of nodes at the current level (levelSize = queue.size()) before starting to process them.
We then dequeue levelSize nodes, and for each node, we enqueue its non-null children.
This process continues until the queue is empty, at which point the depth variable holds the maximum depth of the tree.

1import java.util.LinkedList;2import java.util.Queue;3 4/**5 * Definition for a binary tree node.6 * public class TreeNode {7 *     int val;8 *     TreeNode left;9 *     TreeNode right;10 *     TreeNode() {}11 *     TreeNode(int val) { this.val = val; }12 *     TreeNode(int val, TreeNode left, TreeNode right) {13 *         this.val = val;14 *         this.left = left;15 *         this.right = right;16 *     }17 * }18 */19class Solution {20    public int maxDepth(TreeNode root) {21        if (root == null) {22            return 0;23        }24        25        Queue<TreeNode> queue = new LinkedList<>();26        queue.offer(root);27        int depth = 0;28        29        while (!queue.isEmpty()) {30            int levelSize = queue.size();31            depth++;32            33            for (int i = 0; i < levelSize; i++) {34                TreeNode currentNode = queue.poll();35                36                if (currentNode.left != null) {37                    queue.offer(currentNode.left);38                }39                if (currentNode.right != null) {40                    queue.offer(currentNode.right);41                }42            }43        }44        45        return depth;46    }47}

Complexity

Time

O(N)

Space

O(W)

Trade-offs

Pros

Avoids recursion, thus preventing StackOverflowError on very deep trees.
Can be more space-efficient than DFS for tall and skinny trees (e.g., a linked list-like tree).

Cons

Generally requires more code than the recursive solution.
Can be less space-efficient than DFS for wide and shallow trees (e.g., a complete binary tree where the last level has ~N/2 nodes).

Solutions

Solution

1/** * 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; * } * } */ class Solution { public int maxDepth ( TreeNode root ) { if ( root == null ) { return 0 ; } int l = maxDepth ( root . left ); int r = maxDepth ( root . right ); return 1 + Math . max ( l , r ); } }

1/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number} */ var maxDepth =2  function (root) {3    if (!root) return 0;4    const l = maxDepth(root.left);5    const r = maxDepth(root.right);6    return 1 + Math.max(l, r);7  };

1# 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 : TreeNode ) -> int : if root is None : return 0 l , r = self . maxDepth ( root . left ), self . maxDepth ( root . right ) return 1 + max ( l , r )

1/** * 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 ) return 0 ; int l = maxDepth ( root -> left ), r = maxDepth ( root -> right ); return 1 + max ( l , r ); } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem