Binary Tree Cameras

📋

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
}

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

Focus on handling base cases like single node and small complete trees correctly.

Beware of greedy approaches and off-by-one errors; use three-state DFS carefully.

Optimize your solution to linear time using postorder traversal with states.

t1_01basic

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

Expected1

⏱ Performance - must finish in 2000ms

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

💡 Think about covering nodes with minimal cameras using DFS postorder traversal.

💡 Use three states per node: has camera, covered without camera, not covered.

💡 Place camera at a node if any child is not covered to minimize total cameras.

Why it failed: Returned wrong camera count; likely missed placing camera at critical node covering two children. Fix by implementing postorder DFS with three states and placing camera when child is uncovered.

✓ Correctly computed minimum cameras using three-state DFS postorder traversal.

t1_02basic

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

Expected2

⏱ Performance - must finish in 2000ms

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

💡 Consider how cameras cover parent, self, and children in a balanced tree.

💡 Check if placing cameras at leaf parents reduces total cameras.

💡 Use postorder traversal to decide camera placement bottom-up.

Why it failed: Incorrect camera count; likely greedy approach placing cameras only at leaves or root. Fix by using three-state DFS to place cameras at parents of uncovered leaves.

✓ Correctly placed cameras at parents of leaves to minimize total cameras.

t2_01edge

Input{"root":[0]}

Expected1

⏱ Performance - must finish in 2000ms

Single node tree requires one camera to cover itself.

💡 Check base case when tree has only one node.

💡 A single node is uncovered without a camera.

💡 Place a camera at the single node to cover it.

Why it failed: Returned 0 cameras for single node tree; fix by ensuring single node is covered by placing a camera.

✓ Correctly handled single node tree by placing one camera.

t2_02edge

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

Expected1

⏱ Performance - must finish in 2000ms

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

💡 Consider coverage of root camera over its children.

💡 Check if placing camera at root covers entire tree.

💡 Use postorder traversal to confirm minimal cameras.

Why it failed: Returned more than 1 camera for height 1 complete tree; fix by recognizing root camera covers children.

✓ Correctly placed one camera at root covering entire tree.

t2_03edge

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

Expected2

⏱ Performance - must finish in 2000ms

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

💡 Analyze coverage in skewed tree where nodes have only one child.

💡 Check placing cameras at alternate nodes to cover all.

💡 Use postorder DFS to decide camera placement bottom-up.

Why it failed: Returned incorrect camera count for skewed tree; fix by placing cameras at alternate nodes using three-state DFS.

✓ Correctly placed cameras at alternate nodes in skewed tree.

t3_01corner

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

Expected3

⏱ Performance - must finish in 2000ms

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

💡 Beware of greedy approach placing cameras only at leaves.

💡 Use three-state postorder DFS to decide camera placement.

💡 Place cameras at parents of uncovered nodes, not just leaves.

Why it failed: Returned camera count equal to number of leaves; fix by implementing three-state DFS to place cameras at parents of uncovered nodes.

✓ Avoided greedy trap by placing cameras at parents of uncovered nodes.

t3_02corner

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

Expected3

⏱ Performance - must finish in 2000ms

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

💡 Remember each node can have at most one camera.

💡 Avoid counting multiple cameras on same node.

💡 Use states to track coverage and camera placement per node.

Why it failed: Returned camera count assuming multiple cameras per node; fix by enforcing one camera per node with three-state DFS.

✓ Correctly enforced one camera per node constraint.

t3_03corner

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

Expected3

⏱ Performance - must finish in 2000ms

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

💡 Check coverage states carefully for each node.

💡 Ensure cameras cover parent, self, and children correctly.

💡 Use postorder traversal to propagate coverage states accurately.

Why it failed: Returned fewer cameras than needed due to off-by-one coverage error; fix by correctly updating coverage states in DFS.

✓ Correctly handled coverage states without off-by-one errors.

t4_01performance

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

Expectednull

⏱ 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.

💡 Brute force exponential solutions will time out on large n.

💡 Use O(n) postorder DFS with three states to achieve linear time.

💡 Avoid recomputation by memoizing or using bottom-up traversal.

Why it failed: TLE due to exponential brute force recursion; fix by implementing linear time postorder DFS with three states.

✓ Algorithm runs in O(n) time, passing performance constraints.

Practice

1. Consider the following iterative postorder traversal code to check if a binary tree is balanced. Given the tree: root=1, left=2, right=3, and node 2 has left child 4. What is the value of heights[root] after the traversal completes?

easy

A. 2

B. 1

C. 3

D. 4

Solution

1. Step 1: Trace heights for leaf nodes

   Node 4 is a leaf, so heights[4] = 1.

2. Step 2: Compute heights bottom-up

   Node 2 has left child 4 (height 1) and no right child (height 0), so heights[2] = 1 + max(1,0) = 2. Node 3 is leaf, heights[3] = 1. Root 1 has children heights 2 and 1, so heights[1] = 1 + max(2,1) = 3.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Height of root is max height of subtrees plus one [OK]

Hint: Height of root equals max subtree height plus one [OK]

Common Mistakes:

• Forgetting to add 1 for current node height
• Mixing up left and right subtree heights
• Returning height instead of boolean balance

2. You need to convert a binary tree into a string and then reconstruct the exact same tree from that string. Which approach guarantees that the tree structure, including null children, is preserved and can be reconstructed efficiently?

easy

A. Use level order traversal (BFS) including null markers for missing children, then deserialize by reading nodes level by level.

B. Use a greedy traversal that records only node values without null markers, then reconstruct by inserting nodes in order.

C. Use dynamic programming to store subtree encodings and reconstruct from stored subtrees.

D. Use inorder traversal without null markers and reconstruct by assuming a balanced tree.

Solution

1. Step 1: Understand the need for null markers

   Without null markers, the tree structure cannot be uniquely reconstructed because missing children are ambiguous.

2. Step 2: Recognize BFS with null markers preserves structure

   Level order traversal with null markers records nodes level by level, capturing the exact shape of the tree, enabling correct deserialization.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Level order with null markers uniquely encodes tree structure [OK]

Hint: Null markers are essential to preserve tree shape [OK]

Common Mistakes:

• Ignoring null markers leads to ambiguous deserialization
• Assuming inorder traversal alone can reconstruct arbitrary trees
• Using greedy or DP approaches that don't preserve structure

3. Consider this buggy iterative postorder traversal code:

def postorderTraversal(root):
    result = []
    stack = []
    last_visited = None
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        peek_node = stack[-1]
        if peek_node.right and last_visited == peek_node.right:
            current = peek_node.right
        else:
            result.append(peek_node.val)
            last_visited = stack.pop()
    return result

What is the bug in this code?

medium

A. The inner while loop should traverse right children instead of left

B. The condition should check if last_visited != peek_node.right, not == peek_node.right

C. The last_visited variable is never updated

D. The result list is appended before traversing the left subtree

Solution

1. Step 1: Examine condition for traversing right subtree

   Correct logic requires moving to right child if it exists and was not visited yet, so condition must be last_visited != peek_node.right.

2. Step 2: Identify effect of wrong condition

   Using last_visited == peek_node.right causes skipping right subtree traversal or infinite loops.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Fixing condition restores correct postorder traversal [OK]

Hint: Check last_visited != right child to avoid revisiting [OK]

Common Mistakes:

• Using == instead of !=
• Not updating last_visited
• Appending too early

4. What is the space complexity of the optimal in-place flatten algorithm that uses reverse preorder traversal with a global pointer on a binary tree of n nodes and height h?

medium

A. O(n) due to storing all nodes in a list during traversal

B. O(1) because the algorithm modifies the tree in-place without extra memory

C. O(log n) because the tree height is always balanced and recursion stack is limited

D. O(h) due to recursion stack depth in worst case of skewed tree

Solution

1. Step 1: Identify auxiliary space usage

   The algorithm uses recursion, so space is dominated by recursion stack depth, which is the tree height h.

2. Step 2: Clarify why O(h) not O(1) or O(n)

   It does not store nodes externally (not O(n)) and is not constant space due to recursion stack (not O(1)). For skewed trees, h can be up to n.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Recursion stack space equals tree height h [OK]

Hint: Recursion stack space equals tree height h [OK]

Common Mistakes:

• Assuming O(1) space because of in-place modification
• Confusing recursion stack with explicit data structures
• Assuming balanced tree always so O(log n) space

5. Suppose the problem is modified so that paths can move both downwards and upwards (i.e., any connected path in the tree, not necessarily parent-to-child). Which of the following changes to the algorithm is necessary to correctly count all such paths?

hard

A. Convert the tree to an undirected graph and use DFS from every node with prefix sums, resetting counts after each start.

B. Use the brute force approach checking all paths from every node without prefix sums.

C. Use the same prefix sum DFS approach but run it twice: once from root down and once from leaves up.

D. Modify the prefix sum map to store sums for paths in both directions simultaneously during one DFS.

Solution

1. Step 1: Understand path direction relaxation

   Allowing upward and downward moves means paths are any connected sequences, not just parent-to-child.

2. Step 2: Model tree as undirected graph and run DFS from every node

   To count all paths, treat tree as undirected graph and run DFS from each node, using prefix sums and resetting counts to avoid cross-branch contamination.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Undirected DFS from every node with prefix sums counts all connected paths [OK]

Hint: Undirected graph DFS needed for arbitrary path directions [OK]

Common Mistakes:

• Trying to reuse one-directional prefix sum DFS without modification
• Assuming running DFS twice covers all paths
• Trying to store both directions in one prefix sum map