Bird
Raised Fist0
Interview Preptree-dfshardAmazonGoogle

Binary Tree Cameras

Choose your preparation mode4 modes available
📋
Problem

Imagine you are installing security cameras in a large building represented as a binary tree. Each camera can monitor its parent, itself, and its immediate children. How do you place the minimum number of cameras to cover every room?

Given a binary tree, we need to place cameras on some nodes of the tree. Each camera at a node can monitor its parent, itself, and its immediate children. Return the minimum number of cameras needed to monitor all nodes of the tree.

The number of nodes in the tree is in the range [1, 10^5].Each node's value is unique (not necessarily required but typical).
Edge cases: Single node tree → 1 camera neededComplete binary tree with height 1 → 1 camera neededSkewed tree (all left or all right) → cameras placed at alternate nodes
</>
IDE
def minCameraCover(root: Optional[TreeNode]) -> int:public int minCameraCover(TreeNode root)int minCameraCover(TreeNode* root)function minCameraCover(root)
def minCameraCover(root):
    # Write your solution here
    pass
class Solution {
    public int minCameraCover(TreeNode root) {
        // Write your solution here
        return 0;
    }
}
#include <vector>
using namespace std;

int minCameraCover(TreeNode* root) {
    // Write your solution here
    return 0;
}
function minCameraCover(root) {
    // Write your solution here
}
0/9
Common Bugs to Avoid
Wrong: Number of cameras equal to number of leavesGreedy approach placing cameras only at leaves without considering parents.✅ Implement postorder DFS with three states and place cameras at parents of uncovered nodes.
Wrong: 0 cameras for single node treeNot handling base case where single node must have a camera.✅ Add base case: if node is leaf and uncovered, place camera.
Wrong: More cameras than minimal in complete binary treeNot recognizing that one camera at root covers entire tree.✅ Use postorder DFS to check coverage and avoid redundant cameras.
Wrong: TLE on large inputUsing brute force exponential recursion instead of linear DFS.✅ Use O(n) postorder DFS with three states to achieve linear time complexity.
Wrong: Incorrect camera count due to off-by-one coverage errorMismanagement of coverage states leading to undercounting cameras.✅ Carefully update coverage states in postorder traversal to avoid off-by-one errors.
✓
Test Cases
t1_01basic
Input{"root":[0,0,null,0,0]}
Expected1

Place one camera at the node with two children to cover all nodes.

t1_02basic
Input{"root":[0,0,0,null,0,null,0]}
Expected2

Two cameras needed: one at root's left child and one at root's right child to cover all nodes.

t2_01edge
Input{"root":[0]}
Expected1

Single node tree requires one camera to cover itself.

t2_02edge
Input{"root":[0,0,0]}
Expected1

Complete binary tree of height 1 requires only one camera at root to cover all nodes.

t2_03edge
Input{"root":[0,null,0,null,0,null,0]}
Expected2

Skewed tree (all right children) requires cameras at alternate nodes to cover all.

t3_01corner
Input{"root":[0,0,null,0,null,0,null,0]}
Expected3

Greedy trap: placing cameras only at leaves leads to more cameras than necessary.

t3_02corner
Input{"root":[0,0,0,0,null,null,0,null,null,null,0]}
Expected3

Confusion between 0/1 and unbounded: each node can have at most one camera, no multiple cameras stacked.

t3_03corner
Input{"root":[0,0,0,0,0,null,null,null,null,0,0]}
Expected3

Off-by-one error in coverage calculation leads to undercounting cameras.

t4_01performance
Input{"root":[1,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,10]}
⏱ Performance - must finish in 2000ms

Skewed tree with 10^5 nodes (simulated here with 10 for brevity) tests O(n) complexity; brute force O(2^n) will TLE.

Practice

(1/5)
1. You are given a binary tree where each node contains an integer value (which can be negative). The task is to find the maximum sum of values along any path in the tree, where a path can start and end at any node and must be connected through parent-child links. Which approach guarantees an optimal solution for this problem?
easy
A. Perform a postorder traversal with recursion, tracking the maximum gain from each subtree and updating a global maximum path sum.
B. Enumerate all possible paths in the tree and compute their sums to find the maximum.
C. Use a greedy traversal that picks the maximum child at each node and sums values along that path.
D. Use a breadth-first search (BFS) to find the longest path and sum its node values.

Solution

  1. Step 1: Understand the problem constraints

    The path can start and end at any node, not necessarily the root or leaf, and node values can be negative.
  2. Step 2: Identify the approach that handles all cases optimally

    Postorder recursion allows computing maximum gains from left and right subtrees, considering negative values by ignoring negative gains, and updating a global max path sum that includes both children and the current node.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Postorder recursion with global max handles negative values and arbitrary paths [OK]
Hint: Postorder recursion tracks max gains and global max [OK]
Common Mistakes:
  • Greedy approach fails on negative values and non-root paths
  • Enumerating all paths is inefficient and impractical
  • BFS does not capture arbitrary path sums
2. Consider the following iterative postorder traversal code to compute the maximum path sum in a binary tree. Given the tree below, what is the final value of max_sum after the function completes? Tree structure: ``` 1 / 2 3 ```
class TreeNode:
    def __init__(self, val=0, left=null, right=null):
        self.val = val
        self.left = left
        self.right = right

def maxPathSum(root):
    if not root:
        return 0
    max_sum = float('-inf')
    stack = []
    node = root
    last_visited = null
    gain_map = {}

    while stack or node:
        if node:
            stack.append(node)
            node = node.left
        else:
            peek = stack[-1]
            if peek.right and last_visited != peek.right:
                node = peek.right
            else:
                left_gain = max(gain_map.get(peek.left, 0), 0)
                right_gain = max(gain_map.get(peek.right, 0), 0)
                current_path_sum = peek.val + left_gain + right_gain
                max_sum = max(max_sum, current_path_sum)
                gain_map[peek] = peek.val + max(left_gain, right_gain)
                last_visited = stack.pop()
    return max_sum
easy
A. 5
B. 4
C. 6
D. 3

Solution

  1. Step 1: Trace left subtree gain

    Node 2 has no children, so left_gain=0, right_gain=0, current_path_sum=2, max_sum updated to 2, gain_map[2]=2.
  2. Step 2: Trace root and right subtree

    Node 3 has no children, current_path_sum=3, max_sum updated to 3, gain_map[3]=3. For root 1, left_gain=2, right_gain=3, current_path_sum=1+2+3=6, max_sum updated to 6.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Sum of path 2 -> 1 -> 3 is 6 [OK]
Hint: Sum path 2->1->3 yields max sum 6 [OK]
Common Mistakes:
  • Ignoring one child's gain leads to 5 or 4
  • Off-by-one in gain_map updates
  • Returning partial sums instead of max path sum
3. Given a binary tree, you need to find the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. Which approach guarantees an optimal solution to this problem?
easy
A. Perform a postorder traversal computing heights and update the diameter at each node using recursion with a global variable.
B. Apply dynamic programming with memoization on node pairs to find longest paths.
C. Use a greedy traversal that always chooses the deeper subtree at each node.
D. Calculate the height of the tree and multiply by two to estimate the diameter.

Solution

  1. Step 1: Understand the problem requires the longest path between any two nodes, not necessarily passing through root.

    The diameter can be found by checking the sum of left and right subtree heights at every node.
  2. Step 2: Recognize that a postorder traversal with recursion and a global variable to track diameter updates at each node ensures all paths are considered.

    This approach visits each node once, updating the diameter with left_height + right_height.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Postorder traversal with global diameter update covers all nodes [OK]
Hint: Diameter updates at every node, not just root [OK]
Common Mistakes:
  • Thinking diameter must pass through root
  • Using greedy to pick deeper subtree only
  • Confusing diameter with twice height
4. You are given a binary tree and two nodes within it. You need to find the node that is the deepest common ancestor of both nodes. Which approach guarantees an optimal solution in terms of time and space complexity?
easy
A. Use a brute force approach by finding paths from root to each node and then comparing the paths.
B. Build a parent pointer map for all nodes, then use ancestor sets to find the lowest common ancestor.
C. Apply a greedy algorithm that picks the first common node found during a preorder traversal.
D. Use dynamic programming to store results of subtrees and combine them to find the ancestor.

Solution

  1. Step 1: Understand problem constraints

    The problem requires finding the lowest common ancestor efficiently, ideally in O(n) time and O(n) space.
  2. Step 2: Evaluate approaches

    Brute force (A) is correct but less optimal. Greedy (C) fails because it may pick incorrect ancestors. DP (D) is not applicable here. Building parent pointers and using ancestor sets (B) provides an optimal and clean solution.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Parent pointer + ancestor set approach is standard optimal solution [OK]
Hint: Parent pointers + ancestor sets yield optimal LCA solution [OK]
Common Mistakes:
  • Assuming greedy traversal finds correct LCA
  • Using DP where not applicable
  • Brute force is optimal
5. Suppose you want to extend the serialization/deserialization to support binary trees where nodes can have duplicate values and the tree can be very deep (height > 10,000). Which modification is necessary to ensure correctness and efficiency?
hard
A. Use iterative BFS serialization with null markers and iterative deserialization to avoid recursion stack overflow.
B. Use recursive DFS with memoization to handle duplicates and deep trees efficiently.
C. Switch to preorder traversal without null markers to reduce string size and recursion depth.
D. Serialize only unique node values and reconstruct tree assuming balanced shape.

Solution

  1. Step 1: Identify problem with deep recursion

    Recursive DFS can cause stack overflow on very deep trees.
  2. Step 2: Use iterative BFS with null markers

    Iterative BFS avoids recursion stack issues and null markers preserve structure even with duplicates.
  3. Step 3: Avoid assumptions about uniqueness or balanced shape

    Duplicates require storing all nodes explicitly; balanced assumptions break correctness.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Iterative BFS with null markers handles deep trees and duplicates safely [OK]
Hint: Iterative BFS avoids recursion limits and preserves structure [OK]
Common Mistakes:
  • Removing null markers to save space breaks reconstruction
  • Using recursion on deep trees causes stack overflow
  • Assuming unique values or balanced trees
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