Bird
Raised Fist0
Interview Preptree-dfseasyAmazonFacebookGoogleMicrosoft

Maximum Depth of Binary Tree

Choose your preparation mode4 modes available
📋
Problem

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.

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.
Edge cases: Single node tree → depth is 1Tree with only left children → depth equals number of nodesTree with only right children → depth equals number of nodes
</>
IDE
def maxDepth(root: Optional[TreeNode]) -> int:public int maxDepth(TreeNode root)int maxDepth(TreeNode* root)function maxDepth(root)
def maxDepth(root):
    # Write your solution here
    pass
class Solution {
    public int maxDepth(TreeNode root) {
        // Write your solution here
        return 0;
    }
}
#include <vector>
using namespace std;

int maxDepth(TreeNode* root) {
    // Write your solution here
    return 0;
}
function maxDepth(root) {
    // Write your solution here
}
0/9
Common Bugs to Avoid
Wrong: 0Returning 0 for non-empty tree due to missing base case for null nodes or incorrect initial return.✅ Add base case: if root is None, return 0; otherwise return 1 + max(left_depth, right_depth).
Wrong: 1Returning 1 regardless of subtree depth, ignoring deeper paths.✅ Return 1 + max(depth of left subtree, depth of right subtree) instead of a constant 1.
Wrong: Less than actual depth for skewed treesNot recursing down one side (left or right) fully or stopping early.✅ Ensure recursion visits both left and right children and returns max depth.
Wrong: Stack overflow or TLEExponential recursion or repeated subtree computations.✅ Use simple DFS visiting each node once; avoid recomputing depths of subtrees.
✓
Test Cases
t1_01basic
Input{"root":[3,9,20,null,null,15,7]}
Expected3

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

t1_02basic
Input{"root":[1,2,3,4,5]}
Expected3

The longest path is 1 -> 2 -> 4 or 1 -> 2 -> 5, both have length 3.

t2_01edge
Input{"root":null}
Expected0

Empty tree has depth 0.

t2_02edge
Input{"root":[42]}
Expected1

Single node tree has depth 1.

t2_03edge
Input{"root":[1,2,null,3,null,4,null,5]}
Expected5

Tree with only left children has depth equal to number of nodes (5).

t3_01corner
Input{"root":[1,null,2,null,3,null,4,null,5]}
Expected5

Tree with only right children has depth equal to number of nodes (5).

t3_02corner
Input{"root":[1,2,3,4,null,null,5,null,null,null,6]}
Expected4

Tree with mixed missing children; longest path is 1 -> 3 -> 5 -> 6 with length 4.

t3_03corner
Input{"root":[1,2,3,4,5,6,7,8,null,null,null,null,null,null,9]}
Expected5

Balanced tree with deeper leaf at leftmost branch; longest path length is 5.

t4_01performance
Input{"root":[1,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,10,null,11,null,12,null,13,null,14,null,15,null,16,null,17,null,18,null,19,null,20,null,21,null,22,null,23,null,24,null,25,null,26,null,27,null,28,null,29,null,30,null,31,null,32,null,33,null,34,null,35,null,36,null,37,null,38,null,39,null,40,null,41,null,42,null,43,null,44,null,45,null,46,null,47,null,48,null,49,null,50,null,51,null,52,null,53,null,54,null,55,null,56,null,57,null,58,null,59,null,60,null,61,null,62,null,63,null,64,null,65,null,66,null,67,null,68,null,69,null,70,null,71,null,72,null,73,null,74,null,75,null,76,null,77,null,78,null,79,null,80,null,81,null,82,null,83,null,84,null,85,null,86,null,87,null,88,null,89,null,90,null,91,null,92,null,93,null,94,null,95,null,96,null,97,null,98,null,99,null,100]}
⏱ Performance - must finish in 2000ms

Deep left-skewed tree with n=100 nodes; O(n) time complexity must complete within 2 seconds.

Practice

(1/5)
1. 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
2. What is the time complexity of the optimized recursive solution that uses a hash map for index lookup when constructing a binary tree from inorder and postorder traversals of size n?
medium
A. O(n) because each node is processed once and index lookup is O(1)
B. O(n^2) due to repeated slicing of arrays
C. O(n log n) because of balanced tree recursion depth
D. O(n) but with O(n) auxiliary space for recursion stack and hash map

Solution

  1. Step 1: Analyze time complexity

    Using a hash map avoids repeated linear searches, so each node is processed once -> O(n) time.
  2. Step 2: Analyze space complexity

    Hash map stores n elements, recursion stack can be up to O(n) in skewed trees, so total auxiliary space is O(n).
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Time is O(n), space includes recursion stack and hash map [OK]
Hint: Hash map reduces search to O(1), recursion stack adds O(n) space [OK]
Common Mistakes:
  • Assuming slicing causes O(n^2) time
  • Ignoring recursion stack space
  • Confusing balanced tree depth with complexity
3. What is the space complexity of the Morris Preorder Traversal approach for summing root-to-leaf numbers in a binary tree with n nodes?
medium
A. O(1) because Morris traversal uses threaded binary tree links without extra stack
B. O(n) due to recursion stack in DFS
C. O(h) where h is tree height due to implicit stack usage
D. O(n) because all nodes are visited and stored temporarily

Solution

  1. Step 1: Identify space usage in Morris traversal

    Morris traversal modifies tree pointers temporarily to avoid recursion or explicit stack, so no extra stack space is used.
  2. Step 2: Confirm no auxiliary data structures

    Only constant extra variables (pointers and counters) are used, so space complexity is O(1).
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Morris traversal is known for O(1) space by threading tree [OK]
Hint: Morris traversal avoids recursion and stack [OK]
Common Mistakes:
  • Confusing recursion stack with Morris traversal
  • Assuming O(h) due to tree height
4. Suppose you want to perform inorder traversal on a binary tree where nodes can have parent pointers but no left or right child pointers. Which approach correctly produces the inorder sequence without recursion or extra stack?
hard
A. Use Morris traversal by creating threads on parent pointers instead of child pointers.
B. Use breadth-first search since parent pointers allow level order traversal.
C. Use recursive traversal ignoring parent pointers, which will fail due to missing child links.
D. Use iterative traversal with a pointer to the current node and track previously visited node to decide traversal direction.

Solution

  1. Step 1: Understand traversal constraints

    Without left/right child pointers, Morris traversal is not applicable since it relies on child links.
  2. Step 2: Use parent pointers to simulate traversal

    By tracking current and previously visited nodes, we can move up or down the tree to simulate inorder traversal iteratively.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Tracking previous node enables correct traversal without extra space [OK]
Hint: Parent pointers + prev node tracking enable traversal [OK]
Common Mistakes:
  • Trying to create threads on parent pointers
  • Using recursion without child pointers
  • Confusing BFS with inorder traversal
5. Suppose the binary tree nodes can have duplicate values, and you are given preorder and inorder traversals with duplicates. Which modification to the standard iterative approach is necessary to correctly reconstruct the tree?
hard
A. Use a hash map from value to a list of all indices in inorder, and track which index to use next during construction.
B. Ignore duplicates and build the tree as usual, since preorder and inorder uniquely identify the tree.
C. Sort the preorder array to remove duplicates before building the tree.
D. Use a brute force approach with array slicing to handle duplicates correctly.

Solution

  1. Step 1: Understand the problem with duplicates

    Duplicates cause ambiguity in mapping values to inorder indices, breaking the unique root index lookup.
  2. Step 2: Modify data structure

    Store all indices of each value in a list, and track which occurrence to use next to maintain correct subtree boundaries.
  3. Step 3: Avoid naive approaches

    Ignoring duplicates or sorting breaks traversal properties; brute force is inefficient and unnecessary with proper tracking.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Tracking multiple indices per value resolves duplicate ambiguity [OK]
Hint: Track all inorder indices per value to handle duplicates [OK]
Common Mistakes:
  • Assuming unique values always
  • Sorting preorder breaks tree structure
  • Using brute force causes inefficiency
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