Bird
Raised Fist0
Interview Preptree-dfseasyAmazonFacebookGoogleMicrosoft

Maximum Depth of Binary Tree

Choose your preparation mode4 modes available
▶
Steps
setup

Check if root is null

The algorithm first checks if the root node is null. Since the root exists, it proceeds to initialize the queue.

💡 This step ensures we handle the edge case of an empty tree, which would have depth zero.
Line:if root is None: return 0
💡 The algorithm only proceeds if there is at least one node to process.
📊
Maximum Depth of Binary Tree - Watch the Algorithm Execute, Step by Step
Watching the algorithm process each level of the tree visually helps you understand how BFS explores nodes layer by layer and how depth is measured by counting these layers.
Step 1/14
·Active fill★Answer cell
3920157
3920157
BFS Queue
N0 (L0)
Current node: 0
3920157
BFS Queue
N0 (L0)
3920157
BFS Queue
N1 (L1)N2 (L1)
3920157
BFS Queue
N1 (L1)N2 (L1)
Current node: 1
3920157
BFS Queue
N1 (L1)N2 (L1)
3920157
BFS Queue
N2 (L1)
3920157
BFS Queue
N3 (L2)N4 (L2)
3920157
BFS Queue
N3 (L2)N4 (L2)
Current node: 3
3920157
BFS Queue
N3 (L2)N4 (L2)
3920157
BFS Queue
N4 (L2)
3920157
3920157
3920157
Return: 3

Key Takeaways

✓ Maximum depth corresponds to the number of levels processed in BFS.

This insight is hard to see from code alone because depth is incremented outside the inner loop, which might be overlooked without visualization.

✓ BFS processes nodes level by level, enqueuing children to prepare the next level.

Visualizing the queue contents at each step clarifies how BFS expands the frontier and separates levels.

✓ Leaf nodes do not add children to the queue, signaling the end of branches.

Seeing leaf nodes removed from the queue without enqueuing new nodes helps understand how BFS naturally terminates.

Practice

(1/5)
1. Given the following code for the optimal camera placement, what is the final number of cameras placed for the tree with root node 0, left child 1, and right child 2 (both children are leaves)?
easy
A. 2
B. 0
C. 3
D. 1

Solution

  1. Step 1: Trace dfs on leaf nodes 1 and 2

    Leaves return NOT_COVERED (0) because their children are null and return COVERED_NO_CAM (1). So dfs(1) and dfs(2) return NOT_COVERED.
  2. Step 2: At root node 0, left or right child is NOT_COVERED, so place a camera here

    Increment cameras to 1 and return HAS_CAM (2). The root is covered, so no extra camera needed.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    One camera at root covers all nodes [OK]
Hint: Leaves uncovered -> camera at parent -> minimal cameras [OK]
Common Mistakes:
  • Counting cameras on leaves instead of parent
  • Forgetting to add camera at root if uncovered
  • Misinterpreting coverage states
2. Given a binary tree and a target sum, you need to count all paths where the sum of the node values along the path equals the target. The path can start and end at any node but must go downwards (parent to child). Which approach guarantees an optimal solution in terms of time complexity?
easy
A. Use a brute force DFS starting from every node, checking all downward paths for the target sum.
B. Use dynamic programming to store sums of subtrees and combine results bottom-up.
C. Use a DFS with a prefix sum hash map to track cumulative sums and count valid paths in one traversal.
D. Use a greedy approach to prune paths that exceed the target sum early.

Solution

  1. Step 1: Understand problem constraints and path definition

    The path can start and end anywhere but must go downwards, so checking all paths naively is expensive.
  2. Step 2: Recognize prefix sum with DFS pattern

    Using a prefix sum hash map during DFS allows counting all valid paths in O(n) time by tracking cumulative sums and their frequencies.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Prefix sum + DFS solves in linear time [OK]
Hint: Prefix sums track cumulative sums efficiently [OK]
Common Mistakes:
  • Assuming paths must start at root or leaf
  • Using brute force DFS from every node without pruning
  • Trying greedy pruning which fails on negative values
3. The following code attempts to check if a binary tree is balanced using iterative postorder traversal. Which line contains a subtle bug that can cause incorrect results on an empty tree or null root?
medium
A. Line 1: Missing check for empty root before traversal
B. Line 7: Incorrectly pushing node.left without null check
C. Line 12: Comparing last_visited with peek.right incorrectly
D. Line 16: Using abs difference without considering null children

Solution

  1. Step 1: Identify handling of empty tree

    The code does not check if root is None before starting traversal, which can cause errors or incorrect results.
  2. Step 2: Verify other lines

    Other lines handle null children safely using heights.get with default 0, and last_visited logic is correct.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Missing early return for empty root causes bug [OK]
Hint: Always check for empty root before traversal [OK]
Common Mistakes:
  • Forgetting to handle empty tree as balanced
  • Incorrectly comparing last_visited causing infinite loops
  • Not defaulting heights for null children
4. Suppose the problem is modified so that cameras can monitor nodes up to distance 2 away (i.e., parent, self, children, and grandchildren). Which change to the algorithm is necessary to maintain minimal camera placement?
hard
A. Use the same three-state postorder traversal but add a fourth state to track grandchildren coverage
B. Place cameras greedily on all nodes with uncovered children as before, no change needed
C. Modify DFS to track coverage states up to distance 2 and place cameras accordingly, increasing state complexity
D. Switch to brute force recursion since greedy no longer works

Solution

  1. Step 1: Understand coverage radius increase

    Cameras now cover nodes up to distance 2, so coverage states must reflect grandchildren coverage, not just immediate children.
  2. Step 2: Adjust algorithm states

    The original three states are insufficient; DFS must track coverage at a larger radius, increasing complexity and requiring more nuanced state management.
  3. Step 3: Evaluate options

    Simply adding a fourth state (A) is vague and insufficient without redesign. Greedy placement without state changes (B) fails minimality. Brute force (D) is inefficient and unnecessary.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    Expanded coverage radius requires more complex state tracking [OK]
Hint: Larger coverage radius -> more complex states in DFS [OK]
Common Mistakes:
  • Assuming original states suffice for extended coverage
  • Relying on naive greedy placement
  • Switching to brute force unnecessarily
5. Suppose the problem is extended: the tree nodes can have duplicate values, and you want to check if the tree is symmetric ignoring node values, only structure matters. Which modification to the original DFS approach correctly solves this variant?
hard
A. Keep the value comparison but add a hash map to track visited nodes to avoid duplicates.
B. Use BFS level-order traversal and check if each level forms a palindrome of node values.
C. Modify the base case to return true if both nodes are null, and skip the value comparison step entirely.
D. Perform a preorder traversal and compare the traversal list with its reverse.

Solution

  1. Step 1: Understand the variant ignores node values, only structure matters

    Therefore, the value comparison step must be removed to avoid false negatives due to duplicates.
  2. Step 2: Modify the DFS to only check if both nodes exist or are null, recursively comparing mirrored subtrees

    Return true if both nodes are null; otherwise, recurse on mirrored children without comparing values.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Ignoring values means skipping value checks but preserving mirrored structure checks [OK]
Hint: Ignore values, check only mirrored structure recursively [OK]
Common Mistakes:
  • Keeping value checks causing false negatives
  • Using BFS palindrome checks which fail on structure
  • Using preorder traversal which ignores mirrored structure
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