Bird
Raised Fist0
Interview Preptree-dfseasyAmazonFacebookGoogleMicrosoft

Maximum Depth of Binary Tree

Choose your preparation mode4 modes available
🎯
Maximum Depth of Binary Tree
easyTREEAmazonFacebookGoogle

Imagine you are analyzing the structure of a company's organizational chart represented as a binary tree, and you want to find out how many levels of management exist from the CEO down to the lowest employee.

💡 This problem asks for the maximum depth of a binary tree, which is a fundamental tree property. Beginners often struggle because they don't immediately see how to traverse the tree recursively and combine results from subtrees to get the final answer.
📋
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.

The number of nodes in the tree is in the range [1, 10^5].Node values can be any integer.The tree is not necessarily balanced.
💡
Example
Input"root = [3,9,20,null,null,15,7]"
Output3

The longest path is 3 -> 20 -> 15 or 3 -> 20 -> 7, both have length 3.

  • Single node tree → depth is 1
  • Tree with only left children → depth equals number of nodes
  • Tree with only right children → depth equals number of nodes
  • Empty tree (null root) → depth is 0
⚠️
Common Mistakes
Not handling null root (empty tree) case

Code throws null pointer exception or returns incorrect depth

✅ Add base case to return 0 if root is null

Returning sum of left and right depths instead of max

Incorrect depth calculation, overestimates depth

✅ Use max(left_depth, right_depth) instead of left_depth + right_depth

Not incrementing depth by 1 at current node

Depth is off by one, usually too small

✅ Add 1 to max depth of children before returning

Using BFS but not incrementing depth after each level

Depth remains zero or incorrect

✅ Increment depth counter after processing all nodes at a level

Confusing depth with height or number of edges

Off-by-one errors in output

✅ Clarify definition: depth counts nodes along path, including root and leaf

🧠
Brute Force (Pure Recursion)
💡 Starting with pure recursion helps understand the problem from first principles by exploring every path fully without optimization.

Intuition

The maximum depth of a tree is 1 plus the maximum depth of its left and right subtrees. We recursively compute depths of subtrees and combine them.

Algorithm

  1. If the current node is null, return 0 as depth.
  2. Recursively find the maximum depth of the left subtree.
  3. Recursively find the maximum depth of the right subtree.
  4. Return 1 plus the maximum of the left and right subtree depths.
💡 The recursion naturally breaks the problem into smaller subproblems, but beginners may find it tricky to combine results correctly.
</>
Code
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxDepth(root):
    if root is None:
        return 0
    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)
    return 1 + max(left_depth, right_depth)

# Example usage:
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20, TreeNode(15), TreeNode(7))
    print(maxDepth(root))  # Output: 3
Line Notes
if root is None:Base case: if node is null, depth is zero because no nodes exist here
left_depth = maxDepth(root.left)Recursively compute depth of left subtree
right_depth = maxDepth(root.right)Recursively compute depth of right subtree
return 1 + max(left_depth, right_depth)Add 1 for current node and take max depth from children
public class Solution {
    public static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(sol.maxDepth(root)); // Output: 3
    }
}
Line Notes
if (root == null) return 0;Base case: no node means depth zero
int leftDepth = maxDepth(root.left);Recursively find left subtree depth
int rightDepth = maxDepth(root.right);Recursively find right subtree depth
return 1 + Math.max(leftDepth, rightDepth);Add current node and pick max depth
#include <iostream>
#include <algorithm>
using namespace std;

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

int maxDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return 1 + max(leftDepth, rightDepth);
}

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    cout << maxDepth(root) << endl; // Output: 3
    return 0;
}
Line Notes
if (root == nullptr) return 0;Base case: empty node means depth zero
int leftDepth = maxDepth(root->left);Recursively compute left subtree depth
int rightDepth = maxDepth(root->right);Recursively compute right subtree depth
return 1 + max(leftDepth, rightDepth);Add current node and choose max depth
function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function maxDepth(root) {
    if (root === null) return 0;
    const leftDepth = maxDepth(root.left);
    const rightDepth = maxDepth(root.right);
    return 1 + Math.max(leftDepth, rightDepth);
}

// Example usage:
const root = new TreeNode(3,
    new TreeNode(9),
    new TreeNode(20, new TreeNode(15), new TreeNode(7))
);
console.log(maxDepth(root)); // Output: 3
Line Notes
if (root === null) return 0;Base case: no node means depth zero
const leftDepth = maxDepth(root.left);Recursively find left subtree depth
const rightDepth = maxDepth(root.right);Recursively find right subtree depth
return 1 + Math.max(leftDepth, rightDepth);Add current node and pick max depth
⏱
Complexity
TimeO(n)
SpaceO(h)

We visit each node once, so time is O(n). The recursion stack can go as deep as the height h of the tree, so space is O(h).

💡 For a tree with 1000 nodes, this means roughly 1000 operations and stack depth up to the height, which is efficient for typical interview constraints.
Interview Verdict: Accepted

This approach is efficient and accepted for this problem, making it a solid baseline solution.

🧠
Iterative DFS Using Stack
💡 This approach replaces recursion with an explicit stack to simulate DFS, helping avoid recursion stack overflow and demonstrating iterative tree traversal.

Intuition

Use a stack to traverse nodes depth-first, tracking the depth of each node explicitly, and update the maximum depth encountered.

Algorithm

  1. Initialize a stack with the root node and its depth as 1.
  2. While the stack is not empty, pop a node and its depth.
  3. Update the maximum depth if current depth is greater.
  4. Push the node's children onto the stack with depth + 1.
💡 Tracking depth explicitly is key here, which can be tricky for beginners used to recursion.
</>
Code
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxDepth(root):
    if root is None:
        return 0
    stack = [(root, 1)]
    max_depth = 0
    while stack:
        node, depth = stack.pop()
        if node:
            max_depth = max(max_depth, depth)
            stack.append((node.left, depth + 1))
            stack.append((node.right, depth + 1))
    return max_depth

# Example usage:
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20, TreeNode(15), TreeNode(7))
    print(maxDepth(root))  # Output: 3
Line Notes
if root is None:Handle empty tree edge case
stack = [(root, 1)]Initialize stack with root node and depth 1
node, depth = stack.pop()Pop current node and its depth for processing
max_depth = max(max_depth, depth)Update max depth if current depth is larger
import java.util.Stack;

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

    public int maxDepth(TreeNode root) {
        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();
            if (node != null) {
                maxDepth = Math.max(maxDepth, depth);
                stack.push(new Pair<>(node.left, depth + 1));
                stack.push(new Pair<>(node.right, depth + 1));
            }
        }
        return maxDepth;
    }

    // Simple Pair class since Java 8+ doesn't have built-in Pair
    public static 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; }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(sol.maxDepth(root)); // Output: 3
    }
}
Line Notes
if (root == null) return 0;Handle empty tree
Stack<Pair<TreeNode, Integer>> stack = new Stack<>();Initialize stack to hold nodes with their depths
Pair<TreeNode, Integer> current = stack.pop();Pop node and depth for processing
maxDepth = Math.max(maxDepth, depth);Update max depth if current depth is greater
#include <iostream>
#include <stack>
#include <utility>
using namespace std;

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

int maxDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    stack<pair<TreeNode*, int>> stk;
    stk.push({root, 1});
    int max_depth = 0;
    while (!stk.empty()) {
        auto [node, depth] = stk.top();
        stk.pop();
        if (node) {
            max_depth = max(max_depth, depth);
            stk.push({node->left, depth + 1});
            stk.push({node->right, depth + 1});
        }
    }
    return max_depth;
}

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    cout << maxDepth(root) << endl; // Output: 3
    return 0;
}
Line Notes
if (root == nullptr) return 0;Handle empty tree case
stack<pair<TreeNode*, int>> stk;Stack stores nodes paired with their depth
auto [node, depth] = stk.top();Unpack node and depth from stack top
max_depth = max(max_depth, depth);Update max depth if current depth is larger
function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function maxDepth(root) {
    if (root === null) return 0;
    const stack = [[root, 1]];
    let maxDepth = 0;
    while (stack.length > 0) {
        const [node, depth] = stack.pop();
        if (node !== null) {
            maxDepth = Math.max(maxDepth, depth);
            stack.push([node.left, depth + 1]);
            stack.push([node.right, depth + 1]);
        }
    }
    return maxDepth;
}

// Example usage:
const root = new TreeNode(3,
    new TreeNode(9),
    new TreeNode(20, new TreeNode(15), new TreeNode(7))
);
console.log(maxDepth(root)); // Output: 3
Line Notes
if (root === null) return 0;Handle empty tree
const stack = [[root, 1]];Initialize stack with root and depth 1
const [node, depth] = stack.pop();Pop node and depth for processing
maxDepth = Math.max(maxDepth, depth);Update max depth if current depth is greater
⏱
Complexity
TimeO(n)
SpaceO(h)

Each node is visited once, so time is O(n). The stack can hold up to the height h of the tree, so space is O(h).

💡 This approach avoids recursion but uses similar memory proportional to tree height.
Interview Verdict: Accepted

This iterative approach is equally efficient and useful when recursion depth is a concern.

🧠
Breadth-First Search (Level Order Traversal)
💡 Using BFS to find maximum depth is intuitive because depth corresponds to the number of levels in the tree.

Intuition

Traverse the tree level by level using a queue, incrementing depth after processing each level until all nodes are visited.

Algorithm

  1. If the root is null, return 0.
  2. Initialize a queue and enqueue the root.
  3. While the queue is not empty, process all nodes at the current level.
  4. Increment depth after processing each level.
  5. Return the depth after all levels are processed.
💡 The key is to process nodes level by level, which naturally counts the depth.
</>
Code
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):
    if root is None:
        return 0
    queue = deque([root])
    depth = 0
    while queue:
        level_size = len(queue)
        for _ in range(level_size):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        depth += 1
    return depth

# Example usage:
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20, TreeNode(15), TreeNode(7))
    print(maxDepth(root))  # Output: 3
Line Notes
if root is None:Handle empty tree edge case
queue = deque([root])Initialize queue with root node
for _ in range(level_size):Process all nodes at current level
depth += 1Increment depth after finishing current level
import java.util.LinkedList;
import java.util.Queue;

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

    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            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);
            }
            depth++;
        }
        return depth;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(sol.maxDepth(root)); // Output: 3
    }
}
Line Notes
if (root == null) return 0;Handle empty tree
Queue<TreeNode> queue = new LinkedList<>();Initialize queue for BFS
for (int i = 0; i < levelSize; i++) {Process all nodes at current level
depth++;Increment depth after processing a level
#include <iostream>
#include <queue>
using namespace std;

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

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

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    cout << maxDepth(root) << endl; // Output: 3
    return 0;
}
Line Notes
if (root == nullptr) return 0;Handle empty tree
queue<TreeNode*> q;Initialize queue for BFS
for (int i = 0; i < levelSize; i++) {Process all nodes at current level
depth++;Increment depth after processing a level
function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function maxDepth(root) {
    if (root === null) return 0;
    const queue = [root];
    let depth = 0;
    while (queue.length > 0) {
        let levelSize = queue.length;
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            if (node.left !== null) queue.push(node.left);
            if (node.right !== null) queue.push(node.right);
        }
        depth++;
    }
    return depth;
}

// Example usage:
const root = new TreeNode(3,
    new TreeNode(9),
    new TreeNode(20, new TreeNode(15), new TreeNode(7))
);
console.log(maxDepth(root)); // Output: 3
Line Notes
if (root === null) return 0;Handle empty tree
const queue = [root];Initialize queue with root node
for (let i = 0; i < levelSize; i++) {Process all nodes at current level
depth++;Increment depth after processing a level
⏱
Complexity
TimeO(n)
SpaceO(n)

Each node is visited once, so time is O(n). The queue can hold up to the maximum number of nodes at any level, which can be O(n) in worst case.

💡 For a balanced tree with 1000 nodes, the max width is about 500, so space is manageable.
Interview Verdict: Accepted

BFS is a good alternative to DFS and is especially intuitive for level-based problems.

📊
All Approaches - One-Glance Tradeoffs
💡 For most interviews, the recursive DFS approach is simplest and fastest to implement. Iterative DFS and BFS are useful alternatives if recursion depth is a concern.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute Force (Pure Recursion)O(n)O(h) recursion stackYes (deep recursion)N/AMention and code in most interviews
2. Iterative DFS Using StackO(n)O(h) stackNoN/AGood alternative if recursion is risky
3. BFS Level Order TraversalO(n)O(n) queueNoN/AGood for level-based problems or when BFS is preferred
💼
Interview Strategy
💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach, followed by iterative and BFS methods. Practice coding and testing each approach.

How to Present

Step 1: Clarify the problem and ask about empty tree cases.Step 2: Describe the brute force recursive approach and its base case.Step 3: Discuss iterative DFS to avoid recursion stack issues.Step 4: Present BFS as an alternative that counts levels directly.Step 5: Code your chosen approach and test with edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of tree traversal, recursion base cases, and ability to handle edge cases like empty or skewed trees.

Common Follow-ups

  • What if the tree is very deep? → Use iterative DFS to avoid stack overflow.
  • How to find minimum depth? → Modify BFS to return depth at first leaf node.
💡 These follow-ups test your adaptability and understanding of related tree depth concepts.
🔍
Pattern Recognition

When to Use

1) Problem involves binary tree traversal, 2) Need to measure a property from root to leaves, 3) Keywords like 'maximum depth' or 'height', 4) Requires combining results from subtrees.

Signature Phrases

maximum depthlongest path from root to leafheight of binary tree

NOT This Pattern When

Problems asking for path sums or subtree sums are different patterns involving value aggregation.

Similar Problems

Diameter of Binary Tree - measures longest path between any two nodesBalanced Binary Tree - checks height difference between subtreesMinimum Depth of Binary Tree - finds shortest path to leaf

Practice

(1/5)
1. You need to output all nodes of a binary tree such that each node is processed only after its left and right children have been processed. Which traversal approach guarantees this order?
easy
A. Postorder traversal using depth-first search
B. Preorder traversal using recursion
C. Level-order traversal using a queue
D. Inorder traversal using recursion

Solution

  1. Step 1: Understand traversal order requirements

    Postorder traversal processes left subtree, then right subtree, then the node itself, ensuring children are processed before the parent.
  2. Step 2: Compare with other traversals

    Preorder and inorder do not guarantee children processed before parent; level-order processes nodes by depth, not child-first.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Postorder traversal matches the problem's processing order [OK]
Hint: Postorder processes children before parent [OK]
Common Mistakes:
  • Confusing inorder with postorder
  • Thinking preorder processes children first
2. You are given two arrays representing the preorder and inorder traversal sequences of a binary tree. Which approach guarantees reconstructing the original tree efficiently without redundant subtree searches?
easy
A. Use breadth-first search to build the tree level by level from preorder and inorder arrays.
B. Use a greedy approach that picks nodes based on preorder and attaches them arbitrarily to the left or right.
C. Use dynamic programming to store subtree results and combine them for the full tree.
D. Use recursion with a hash map to quickly find root indices in inorder traversal, avoiding repeated searches.

Solution

  1. Step 1: Understand the problem constraints

    Reconstructing a binary tree from preorder and inorder requires knowing root positions quickly to split subtrees.
  2. Step 2: Identify the optimal approach

    Using a hash map for inorder indices allows O(1) root lookups, avoiding repeated O(n) searches in recursion.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Hash map lookup avoids repeated scanning [OK]
Hint: Hash map lookup avoids repeated inorder searches [OK]
Common Mistakes:
  • Assuming greedy or BFS can reconstruct tree correctly
  • Confusing DP with tree construction
  • Ignoring the need for quick root index lookup
3. Given the following code for inverting a binary tree, what is the value of the left child of the root node after calling invertTree(root) on the tree below? Tree structure before inversion:

    2
   / \
  1   3
easy
A. 3
B. 1
C. 2
D. null

Solution

  1. Step 1: Trace recursive calls on root=2

    invertTree called on left child (1) and right child (3), both leaves, so their children are null and return immediately.
  2. Step 2: Swap left and right children of root=2

    After recursion, root.left and root.right are swapped: left becomes 3, right becomes 1.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Root's left child after inversion is original right child 3 [OK]
Hint: Swapping children after recursion flips subtree positions [OK]
Common Mistakes:
  • Confusing left and right child values after inversion
  • Forgetting to swap after recursive calls
  • Assuming root value changes
4. Consider the following Python code implementing the Morris Preorder Traversal approach to sum root-to-leaf numbers. Given the binary tree: 1 / \ 2 3 What is the final value of the variable total returned by sumNumbers?
easy
A. 5
B. 15
C. 25
D. 26

Solution

  1. Step 1: Trace path 1->2

    current_number accumulates 1 then 12; leaf node 2 adds 12 to total.
  2. Step 2: Trace path 1->3

    current_number resets to 1, then accumulates 13; leaf node 3 adds 13 to total. Total = 12 + 13 = 25.
  3. Step 3: Check for off-by-one or missed increments

    Integer division after visiting left subtree correctly adjusts current_number; no extra addition occurs.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    Sum of 12 and 13 is 25, matching code behavior [OK]
Hint: Trace current_number updates carefully at each node [OK]
Common Mistakes:
  • Off-by-one in current_number division
  • Adding non-leaf nodes to total
5. Suppose the Path Sum problem is modified so that node values can be negative, and you want to find if any root-to-leaf path sums exactly to targetSum. Which of the following changes to the DFS approach is necessary to handle this correctly?
hard
A. Precompute all path sums and store them in a hash set for O(1) lookup
B. Add memoization to avoid revisiting nodes with the same current sum
C. Use BFS instead of DFS to guarantee shortest path sum
D. Remove early stopping because negative values can invalidate pruning assumptions

Solution

  1. Step 1: Understand impact of negative values

    Negative values mean partial sums can decrease later, so pruning based on current sum is unsafe.
  2. Step 2: Adjust algorithm accordingly

    Early stopping based on partial sums must be removed to avoid missing valid paths.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Negative values break pruning assumptions, so early stopping must be disabled [OK]
Hint: Negative values invalidate pruning, so no early stopping [OK]
Common Mistakes:
  • Assuming early stopping always works
  • Switching to BFS unnecessarily
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard