Maximum Depth of Binary Tree

📋

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
}

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

Try testing your code on empty and single-node trees to ensure base cases are handled.

Consider trees skewed to one side and with missing children to catch subtle bugs.

Prepare for large inputs; optimize your recursion and avoid repeated work.

t1_01basic

Input{"root":[3,9,20,null,null,15,7]}

Expected3

⏱ Performance - must finish in 2000ms

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

💡 Think about how to traverse the tree to find the longest path from root to leaf.

💡 Use depth-first search (DFS) and compute max depth of left and right subtrees.

💡 Return 1 + max(depth of left subtree, depth of right subtree).

Why it failed: Returned incorrect depth; likely forgot to add 1 for current node or mishandled null nodes. Fix by returning 0 for null and 1 + max(left, right) otherwise.

✓ Correctly computes max depth using DFS recursion.

t1_02basic

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

Expected3

⏱ Performance - must finish in 2000ms

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

💡 Check both left and right children recursively to find max depth.

💡 Remember to handle nodes with only one child correctly.

💡 Return 1 + max(depth of left subtree, depth of right subtree).

Why it failed: Incorrect depth likely due to ignoring one subtree or not adding 1 for current node. Fix by always returning 1 + max(left, right).

✓ Correctly handles trees with missing children.

t2_01edge

Input{"root":null}

Expected0

⏱ Performance - must finish in 2000ms

Empty tree has depth 0.

💡 Consider what the depth should be if the root is null.

💡 Base case: if node is null, return 0.

💡 Ensure your code returns 0 for null root instead of error or wrong value.

Why it failed: Returned non-zero for null root; fix by adding base case: if root is None, return 0.

✓ Correctly returns 0 for empty tree.

t2_02edge

Input{"root":[42]}

Expected1

⏱ Performance - must finish in 2000ms

Single node tree has depth 1.

💡 Check how your code handles a tree with only one node.

💡 Depth should be 1 when root is not null and has no children.

💡 Return 1 + max(0, 0) = 1 for leaf nodes.

Why it failed: Returned 0 or incorrect value for single node; fix by returning 1 + max(left, right) where left and right are 0 for leaf.

✓ Correctly returns 1 for single node tree.

t2_03edge

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

Expected5

⏱ Performance - must finish in 2000ms

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

💡 Test trees skewed to one side to check depth calculation.

💡 Depth should count all nodes along the longest path.

💡 Ensure recursion correctly traverses down left children and counts depth.

Why it failed: Returned less than actual depth for skewed tree; fix by correctly recursing down left subtree and adding 1 at each node.

✓ Correctly computes depth for left-skewed tree.

t3_01corner

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

Expected5

⏱ Performance - must finish in 2000ms

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

💡 Check if your code handles right-skewed trees similarly to left-skewed.

💡 Depth should count nodes along the longest path even if only right children exist.

💡 Ensure recursion visits right child and adds 1 at each node.

Why it failed: Returned less than actual depth for right-skewed tree; fix by recursing down right subtree and adding 1 at each node.

✓ Correctly computes depth for right-skewed tree.

t3_02corner

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

Expected4

⏱ Performance - must finish in 2000ms

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

💡 Test trees with missing children on different sides.

💡 Depth is max of left and right subtree depths plus 1.

💡 Ensure code does not assume both children exist and handles nulls properly.

Why it failed: Incorrect depth due to assuming both children exist; fix by checking for null children before recursion.

✓ Correctly handles trees with missing children.

t3_03corner

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

Expected5

⏱ Performance - must finish in 2000ms

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

💡 Check if your code correctly finds the deepest leaf even if unbalanced.

💡 Depth is max depth of left and right subtrees plus 1.

💡 Ensure recursion explores all paths and returns max depth.

Why it failed: Returned depth of balanced subtree instead of deepest leaf; fix by taking max of left and right subtree depths.

✓ Correctly finds max depth in unbalanced tree.

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]}

Expectednull

⏱ Performance - must finish in 2000ms

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

💡 The algorithm should run in linear time O(n).

💡 Avoid exponential or repeated work by using simple recursion or iterative DFS.

💡 Stack overflow may occur if recursion depth is too large; consider iterative approach if needed.

Why it failed: TLE due to exponential or repeated subtree computations; fix by using memoization or simple DFS with O(n) complexity.

✓ Algorithm runs in O(n) time and handles deep recursion efficiently.

Practice

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 inorder and postorder traversal sequences of a binary tree. Which approach guarantees reconstructing the original tree efficiently without redundant searches?

easy

A. Use a greedy approach by always attaching nodes as left children when possible.

B. Use dynamic programming to store subtrees and avoid recomputation.

C. Use recursion with a hash map to quickly find root indices in the inorder array.

D. Use breadth-first search to reconstruct the tree level by level.

Solution

1. Step 1: Understand the problem constraints

   Reconstructing a tree from inorder and postorder requires identifying root nodes and splitting subtrees efficiently.

2. Step 2: Evaluate approaches

   Recursion with a hash map allows O(1) root index lookup in inorder, avoiding repeated linear searches and ensuring O(n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Hash map lookup avoids O(n) search per recursion [OK]

Hint: Hash map lookup avoids repeated linear searches [OK]

Common Mistakes:

• Assuming greedy or BFS can reconstruct tree uniquely
• Confusing DP with tree construction
• Ignoring index lookup cost

3. You are given a binary tree that is complete (all levels except possibly the last are fully filled, and nodes in the last level are as far left as possible). You need to count the total number of nodes efficiently. Which approach guarantees the optimal time complexity for this problem?

easy

A. Perform a simple DFS traversal counting all nodes, which takes O(n) time.

B. Use the tree height to check if subtrees are perfect and recursively count nodes, achieving O((log n)^2) time.

C. Apply a greedy approach by counting nodes level by level until the last incomplete level.

D. Use a breadth-first search (BFS) traversal to count nodes, which is efficient for complete trees.

Solution

1. Step 1: Understand the problem constraints

   The tree is complete, so the height can be used to identify perfect subtrees quickly.

2. Step 2: Recognize the optimal approach

   Using the height to check if left or right subtree is perfect allows skipping large parts of the tree, reducing complexity to O((log n)^2).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Optimal approach leverages tree height and completeness [OK]

Hint: Use tree height to skip perfect subtrees [OK]

Common Mistakes:

• Assuming BFS or simple DFS is optimal
• Using greedy level counting without height checks

4. You are given a binary tree and a target sum. You need to determine if there exists a root-to-leaf path such that adding up all the values along the path equals the target sum. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Depth-first search (DFS) with early stopping upon finding a valid path

B. Greedy traversal choosing the child with the closest value to the target sum

C. Dynamic programming with memoization of partial sums at each node

D. Breadth-first search (BFS) exploring all paths level by level

Solution

1. Step 1: Understand the problem constraints

   The problem requires checking if any root-to-leaf path sums to the target. This naturally fits a tree traversal pattern.

2. Step 2: Identify the best approach

   DFS with early stopping is optimal because it explores paths deeply and stops as soon as a valid path is found, avoiding unnecessary work.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DFS explores paths fully and stops early when possible [OK]

Hint: Early stopping DFS avoids unnecessary traversal [OK]

Common Mistakes:

• Believing greedy approach works for sums
• Confusing BFS with DFS for path sums

5. Consider this modified code snippet for the Binary Tree Cameras problem. Which line contains the subtle bug that causes incorrect camera placement?

medium

A. Line returning COVERED_NO_CAM after placing a camera instead of HAS_CAM

B. Line returning NOT_COVERED at the end of dfs

C. Line checking if dfs(root) == NOT_COVERED after traversal

D. Line returning COVERED_NO_CAM when node is null

Solution

1. Step 1: Identify camera placement logic

   When a child is NOT_COVERED, a camera must be placed at current node and dfs must return HAS_CAM to indicate camera presence.

2. Step 2: Locate incorrect return

   The code returns COVERED_NO_CAM after placing a camera, which falsely signals no camera here, causing parents to misinterpret coverage.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Returning HAS_CAM is essential after placing a camera [OK]

Hint: Return HAS_CAM after placing camera to signal coverage [OK]

Common Mistakes:

• Returning COVERED_NO_CAM instead of HAS_CAM after camera placement
• Forgetting to add camera if root uncovered
• Mixing coverage states in conditions