Binary Tree Cameras
Asked at DE Shaw
Problem
Binary Tree Cameras asks for the minimum number of cameras to place on nodes so that every node is monitored, where a camera covers its own node, its parent, and its children. The optimal strategy is a greedy post-order pass: never put a camera on a leaf — put it on the leaf's parent instead.
Asked At
| Company | Difficulty | |
|---|---|---|
| DE Shaw | Hard | View all DE Shaw questions → |
How to Think About It
Placing a camera on a leaf covers only the leaf and its parent. Placing it on the leaf's parent covers the leaf, the parent, and the grandparent — strictly better.
Key insight: process bottom-up (post-order) and have each node report one of three states to its parent: 0 = not covered, 1 = has a camera, 2 = covered without a camera.
Rules at a node: if any child is 0 (uncovered), this node must hold a camera -> return 1. Else if any child is 1, this node is covered -> return 2. Otherwise both children are covered but neither can see this node -> return 0 and let the parent handle it.
Null children count as covered (2) so leaves correctly report 0.
After the traversal, if the root itself reports 0, add one more camera at the root.
Optimal Approach
Step 1: cameras = 0.
Step 2: dfs(node):
If node is null, return 2.
l = dfs(node.left), r = dfs(node.right).
If l == 0 or r == 0: cameras += 1; return 1.
If l == 1 or r == 1: return 2.
Return 0.
Step 3: If dfs(root) == 0, cameras += 1.
Step 4: Return cameras.
Time: O(n). Space: O(h).
What Trips People Up in Real Interviews
Greedily putting cameras on leaves or on every other level. Both overcount; the parent-of-leaf rule is what makes the greedy optimal.
Treating null children as uncovered. That forces cameras onto every leaf.
Forgetting the root check at the end. A root whose children are covered but have no camera is left unmonitored.
Checking the "has camera" case before the "uncovered child" case. An uncovered child must win — it forces a camera here.
Solution Code
def minCameraCover(root):
cameras = 0
def dfs(node):
nonlocal cameras
if not node:
return 2
l = dfs(node.left)
r = dfs(node.right)
if l == 0 or r == 0:
cameras += 1
return 1
if l == 1 or r == 1:
return 2
return 0
if dfs(root) == 0:
cameras += 1
return camerasFrequently Asked Questions
What is the Binary Tree Cameras problem?
Binary Tree Cameras asks for the minimum number of cameras to place on nodes so that every node is monitored, where a camera covers its own node, its parent, and its children. The optimal strategy is a greedy post-order pass: never put a camera on a leaf — put it on the leaf's parent instead.
How do you solve Binary Tree Cameras?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Binary Tree Cameras?
Binary Tree Cameras is asked at DE Shaw. It is a hard difficulty problem.
What are common mistakes on Binary Tree Cameras?
- Greedily putting cameras on leaves or on every other level. Both overcount; the parent-of-leaf rule is what makes the greedy optimal.
- Treating null children as uncovered. That forces cameras onto every leaf.
- Forgetting the root check at the end. A root whose children are covered but have no camera is left unmonitored.
- Checking the "has camera" case before the "uncovered child" case. An uncovered child must win — it forces a camera here.