8. Maximum Depth of Binary Tree
easyAsked at LINEReturn the maximum depth of a binary tree — LINE asks this to gauge whether you instinctively reach for recursion before BFS when the input is a tree.
By Sam K., Founder, InterviewChamp.AI · Last verified
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.
Constraints
Number of nodes in the tree is in [0, 10^4]-100 <= Node.val <= 100
Examples
Example 1
root = [3,9,20,null,null,15,7]3Example 2
root = [1,null,2]2Approaches
1. BFS level count
Run a queue-based BFS and increment depth for every full level processed.
- Time
- O(n)
- Space
- O(n)
let q=[root], d=0;
while(q.length && q[0]){
const next=[];
for(const n of q){ if(n.left)next.push(n.left); if(n.right)next.push(n.right); }
q=next; d++;
}
return d;Tradeoff:
2. Recursive DFS
Depth of a node equals one plus the max depth of its children. Recurse and return the larger subtree depth plus one.
- Time
- O(n)
- Space
- O(h)
function maxDepth(root) {
if (!root) return 0;
return 1 + Math.max(
maxDepth(root.left),
maxDepth(root.right)
);
}Tradeoff:
LINE-specific tips
At LINE, link tree depth to chat-thread reply nesting — they like candidates who picture the data structure inside a real product surface.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.