Binary Tree Cameras (LeetCode 968)
You're placing security cameras on the nodes of the root binary tree. Each camera watches three things at once: the node it sits on, that node's parent, and that node's direct children.
Figure out the fewest cameras that still leave no node unwatched.
Worked Examples
root = [0,0,null,0,0]1root = [0,0,null,0,null,0,null,null,0]2⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range [1, 1000].Node.val == 0
Core Insight
Model each subtree's status as a tri-state code instead of a number. A null child returns COVERED. A node whose child NEEDS_CAMERA must place one and return HAS_CAMERA; a node with a HAS_CAMERA child returns COVERED; otherwise it returns NEEDS_CAMERA and lets its parent decide. The root needs one final correction if it still reports NEEDS_CAMERA.
Real-World Scenario & Production Applications
Physical security camera placement in building floor plans, minimum sensor coverage for network topology monitoring.
Subproblems & Recurrence Decomposition3 Phases
An absent child makes no demand: it returns COVERED so a leaf's parent is never forced into an unnecessary camera.
if not node:
return COVERED| 1 | if not node: |
| 2 | return COVERED |
| 3 | left_state, right_state = dfs(node.left), dfs(node.right) |
| 4 | if left_state == NEEDS_CAMERA or right_state == NEEDS_CAMERA: |
| 5 | cameras += 1 |
| 6 | return HAS_CAMERA |
| 7 | if left_state == HAS_CAMERA or right_state == HAS_CAMERA: |
| 8 | return COVERED |
| 9 | return NEEDS_CAMERA |
Conceptual Narrative
🧠 Pattern Intuition & Real-World Analogy
Every earlier DFS archetype in this pattern returned a number upward. This one returns a discrete status code — and the parent's entire job is to react correctly to that code, greedily, without ever looking further than one level down.
📹 The Analogy: A Building Security Manager Who Only Escalates When Forced
Imagine a security manager inspecting a building floor by floor from the ground up, deciding where to mount cameras. At each floor, they ask their two direct subordinates (the children) for a one-word status report: "I'm being watched," "I have my own camera," or "I'm not covered by anything." If either subordinate reports "not covered," the manager must immediately mount a camera on the current floor — waiting even one floor longer risks that uncovered floor never getting seen. If neither subordinate needs help but one already has a camera, the current floor is automatically watched by that camera too (cameras see one level up). Only if both subordinates are already covered without handing this floor any coverage does the current floor pass its own problem up to its own manager above.
🔑 The Key Idea in the Code
The trick is that NEEDS_CAMERA is never acted upon by the node that reports it — it is only ever acted upon by that node's parent, one level up. This one-level delay is exactly what makes the placement greedy-optimal: a node never pre-emptively places a camera "just in case," it only places one the instant a child proves it is truly necessary.
Naive leaf-first camera placement: Placing a camera on every leaf covers each leaf redundantly. Placing on the parent of a group of leaves is always at least as good, since one camera then covers the parent, all its children, and (via the grandparent check) contributes toward the level above.
Null child returning NEEDS_CAMERA instead of COVERED: If an absent child incorrectly reports
NEEDS_CAMERA, every leaf's parent is forced to place an unnecessary camera. A null node must returnCOVERED-- it makes no demand.Forgetting the root correction: The root has no parent to greedily place a camera on its behalf. If
dfs(root)returnsNEEDS_CAMERA, one additional camera must be added after the traversal completes, or the root itself is left unwatched.Acting on NEEDS_CAMERA one level too early: The node that reports
NEEDS_CAMERAmust never place a camera on itself -- only its parent, one level up, is allowed to react to that status. Reacting at the wrong level breaks the greedy-optimality argument.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Minimum number of cameras to monitor a binary tree, a camera watches itself plus its parent plus its children.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: a camera is placed as low in the tree as possible -- only in reaction to a child that has proven it needs one, never pre-emptively.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I define three states -- NEEDS_CAMERA, HAS_CAMERA, COVERED -- and a postorder helper
dfs(node): a null node returns COVERED. Otherwise I recurse into both children first. If either child reports NEEDS_CAMERA, I place a camera here, increment my counter, and return HAS_CAMERA. Else if either child reports HAS_CAMERA, I return COVERED. Otherwise both children are covered but nothing watches me, so I return NEEDS_CAMERA and let my parent decide. After the traversal, if the root itself came back NEEDS_CAMERA, I add one final camera since it has no parent to rely on. Runs inO(N)time and O(H) stack space.
Complexity & Mathematical Proof
O(N)
Look at dfs(node): each node is visited once, makes two child calls and does at most two constant-time state comparisons before returning one of three codes. N nodes × O(1) work = O(N).
O(H) Auxiliary
Only the recursion stack grows, one frame per level of the current root-to-node path, so auxiliary space is the tree height H. The camera counter is a single integer.
T(N) = N · O(1) = O(N)
Derivation Progression
N node visits
Every node is entered once, after both children have reported their state.
O(1) Work Per Frame≤ 2 state comparisons
The parent reacts to two small codes; no subtree is ever re-read.
O(N)
N frames with constant work each, plus one constant-time root correction.
Variable Definitions
Total number of nodes in the binary tree
Tree height (log N in a balanced tree, N in a skewed tree)
Memory Architecture & Bounds
O(H) recursion frames
O(1) counter and three state constants
O(1) returns one integer
Boundary Best / Worst Cases
time with stack on a balanced tree.
time.
time with stack on a skewed tree.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "minimum number of cameras", "a camera monitors its parent, itself, and its children". Postorder Greedy Tri-State Covering: instead of returning a number, each subtree reports one of three discrete states -- NEEDS_CAMERA, HAS_CAMERA, or COVERED -- and the parent greedily reacts to that state.
. Time budget is strictly , one postorder pass with no revisits.
Binary Tree Cameras (LeetCode 968)
You're placing security cameras on the nodes of the root binary tree. Each camera watches three things at once: the node it sits on, that node's parent, and that node's direct children.
Figure out the fewest cameras that still leave no node unwatched.
Worked Examples
root = [0,0,null,0,0]1root = [0,0,null,0,null,0,null,null,0]2⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range [1, 1000].Node.val == 0
Core Insight
Model each subtree's status as a tri-state code instead of a number. A null child returns COVERED. A node whose child NEEDS_CAMERA must place one and return HAS_CAMERA; a node with a HAS_CAMERA child returns COVERED; otherwise it returns NEEDS_CAMERA and lets its parent decide. The root needs one final correction if it still reports NEEDS_CAMERA.
Real-World Scenario & Production Applications
Physical security camera placement in building floor plans, minimum sensor coverage for network topology monitoring.
Subproblems & Recurrence Decomposition3 Phases
An absent child makes no demand: it returns COVERED so a leaf's parent is never forced into an unnecessary camera.
if not node:
return COVERED| 1 | if not node: |
| 2 | return COVERED |
| 3 | left_state, right_state = dfs(node.left), dfs(node.right) |
| 4 | if left_state == NEEDS_CAMERA or right_state == NEEDS_CAMERA: |
| 5 | cameras += 1 |
| 6 | return HAS_CAMERA |
| 7 | if left_state == HAS_CAMERA or right_state == HAS_CAMERA: |
| 8 | return COVERED |
| 9 | return NEEDS_CAMERA |
Conceptual Narrative
🧠 Pattern Intuition & Real-World Analogy
Every earlier DFS archetype in this pattern returned a number upward. This one returns a discrete status code — and the parent's entire job is to react correctly to that code, greedily, without ever looking further than one level down.
📹 The Analogy: A Building Security Manager Who Only Escalates When Forced
Imagine a security manager inspecting a building floor by floor from the ground up, deciding where to mount cameras. At each floor, they ask their two direct subordinates (the children) for a one-word status report: "I'm being watched," "I have my own camera," or "I'm not covered by anything." If either subordinate reports "not covered," the manager must immediately mount a camera on the current floor — waiting even one floor longer risks that uncovered floor never getting seen. If neither subordinate needs help but one already has a camera, the current floor is automatically watched by that camera too (cameras see one level up). Only if both subordinates are already covered without handing this floor any coverage does the current floor pass its own problem up to its own manager above.
🔑 The Key Idea in the Code
The trick is that NEEDS_CAMERA is never acted upon by the node that reports it — it is only ever acted upon by that node's parent, one level up. This one-level delay is exactly what makes the placement greedy-optimal: a node never pre-emptively places a camera "just in case," it only places one the instant a child proves it is truly necessary.
Naive leaf-first camera placement: Placing a camera on every leaf covers each leaf redundantly. Placing on the parent of a group of leaves is always at least as good, since one camera then covers the parent, all its children, and (via the grandparent check) contributes toward the level above.
Null child returning NEEDS_CAMERA instead of COVERED: If an absent child incorrectly reports
NEEDS_CAMERA, every leaf's parent is forced to place an unnecessary camera. A null node must returnCOVERED-- it makes no demand.Forgetting the root correction: The root has no parent to greedily place a camera on its behalf. If
dfs(root)returnsNEEDS_CAMERA, one additional camera must be added after the traversal completes, or the root itself is left unwatched.Acting on NEEDS_CAMERA one level too early: The node that reports
NEEDS_CAMERAmust never place a camera on itself -- only its parent, one level up, is allowed to react to that status. Reacting at the wrong level breaks the greedy-optimality argument.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Minimum number of cameras to monitor a binary tree, a camera watches itself plus its parent plus its children.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: a camera is placed as low in the tree as possible -- only in reaction to a child that has proven it needs one, never pre-emptively.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I define three states -- NEEDS_CAMERA, HAS_CAMERA, COVERED -- and a postorder helper
dfs(node): a null node returns COVERED. Otherwise I recurse into both children first. If either child reports NEEDS_CAMERA, I place a camera here, increment my counter, and return HAS_CAMERA. Else if either child reports HAS_CAMERA, I return COVERED. Otherwise both children are covered but nothing watches me, so I return NEEDS_CAMERA and let my parent decide. After the traversal, if the root itself came back NEEDS_CAMERA, I add one final camera since it has no parent to rely on. Runs inO(N)time and O(H) stack space.
Complexity & Mathematical Proof
O(N)
Look at dfs(node): each node is visited once, makes two child calls and does at most two constant-time state comparisons before returning one of three codes. N nodes × O(1) work = O(N).
O(H) Auxiliary
Only the recursion stack grows, one frame per level of the current root-to-node path, so auxiliary space is the tree height H. The camera counter is a single integer.
T(N) = N · O(1) = O(N)
Derivation Progression
N node visits
Every node is entered once, after both children have reported their state.
O(1) Work Per Frame≤ 2 state comparisons
The parent reacts to two small codes; no subtree is ever re-read.
O(N)
N frames with constant work each, plus one constant-time root correction.
Variable Definitions
Total number of nodes in the binary tree
Tree height (log N in a balanced tree, N in a skewed tree)
Memory Architecture & Bounds
O(H) recursion frames
O(1) counter and three state constants
O(1) returns one integer
Boundary Best / Worst Cases
time with stack on a balanced tree.
time.
time with stack on a skewed tree.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "minimum number of cameras", "a camera monitors its parent, itself, and its children". Postorder Greedy Tri-State Covering: instead of returning a number, each subtree reports one of three discrete states -- NEEDS_CAMERA, HAS_CAMERA, or COVERED -- and the parent greedily reacts to that state.
. Time budget is strictly , one postorder pass with no revisits.