Binary Tree Cameras (LeetCode 968)
Postorder Greedy Tri-State Covering: Cameras Placed As Low As Possible
You are given the root of a binary tree. We install cameras on the tree nodes where 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.
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
Why It Works & Core Invariant
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
Establish initial problem boundaries and state invariants such that the valid search space is fully bounded.
lo, hi = 0, len(items) - 1| 1 | if not node: return COVERED |
| 2 | left_state, right_state = dfs(node.left), dfs(node.right) |
| 3 | if left_state == NEEDS_CAMERA or right_state == NEEDS_CAMERA: |
| 4 | cameras += 1; return HAS_CAMERA |
| 5 | if left_state == HAS_CAMERA or right_state == HAS_CAMERA: return COVERED |
| 6 | return NEEDS_CAMERA |
Target: Binary Tree Cameras (LeetCode 968). An absent child never forces a camera -- it is trivially covered
Subtree bottom-up aggregation: a node combines child subtree solutions upon backtrack; top-down invariants pass accumulated state down the path.
Base case: if not node: return base; recursive calls on left/right child nodes.
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.
🪄 Breaking Down the Code's "Magic Trick"
NEEDS_CAMERA, HAS_CAMERA, COVERED = 0, 1, 2 def dfs(node): if not node: return COVERED # an absent child can never demand a camera left, right = dfs(node.left), dfs(node.right) if left == NEEDS_CAMERA or right == NEEDS_CAMERA: cameras[0] += 1 return HAS_CAMERA # place greedily, as low as possible if left == HAS_CAMERA or right == HAS_CAMERA: return COVERED # a neighboring camera already sees this node return NEEDS_CAMERA # covered nowhere -- let the parent decide 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.
💡 Summary
When a tree problem's decision at one node depends only on a small, enumerable set of statuses reported by its children (not raw values), model the return value as a tri-state (or n-state) code and let each parent react greedily to exactly what its children report — this collapses what looks like a combinatorial covering problem into a single linear postorder pass.
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
You will see how a postorder tri-state code (uncovered / has-camera / covered) lets each parent greedily decide whether it must place a camera.
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
Placing a camera on every leaf: wasteful. A leaf's parent can cover it (and any siblings) with a single camera instead.
Returning NEEDS_CAMERA for a null child: forces every leaf's parent into an unnecessary camera. A null node must return COVERED.
Forgetting the root correction: the root has no parent to place a camera for it. If
dfs(root)returns NEEDS_CAMERA, one final camera must be added after the traversal.
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.
So: null returns COVERED; a NEEDS_CAMERA child forces the parent to place a camera (HAS_CAMERA); a HAS_CAMERA child naturally covers the parent (COVERED); otherwise the parent reports NEEDS_CAMERA upward.
Complexity & Mathematical Proof
O(N)
Look at the recursive function: `def maxDepth(node):`. For every node in the binary tree, the function executes exactly 2 recursive calls (`maxDepth(node.left)` and `maxDepth(node.right)`) and performs O(1) constant-time arithmetic combining their results (`1 + max(left, right)`). Because each of the N tree nodes is visited and processed exactly once, total time is N · O(1) = O(N).
O(H) Auxiliary
Look at the recursion call stack: Each recursive call adds a new stack frame storing the local `node` pointer. The maximum number of simultaneous stack frames alive at any instant equals the maximum path depth from root to leaf, which is the tree height H. In a balanced binary tree, H = log2(N) -> O(log N) stack memory. In a worst-case skewed tree (linked list), H = N -> O(N) stack memory. We allocate zero heap objects, so auxiliary space is bounded by tree height O(H).
T(N) = 2T(N/2) + O(1) ⟹ O(N)
Look at the recursive function: def maxDepth(node):. For every node in the binary tree, the function executes exactly 2 recursive calls (maxDepth(node.left) and maxDepth(node.right)) and performs O(1) constant-time arithmetic combining their results (1 + max(left, right)). Because each of the N tree nodes is visited and processed exactly once, total time is N · O(1) = O(N).
Derivation Progression
N nodes visited
Every node in the binary tree is entered and exited exactly once.
1 + max(left, right)
Combining child subproblem depths requires a single addition and max comparison in O(1).
T(N) = 2T(N/2) + O(1) ⟹ O(N)
Visiting all N nodes with constant combining work yields strictly O(N) time.
Variable Definitions
Memory Architecture & Bounds
O(H) Recursion stack storing tree height H frames (O(log N) balanced, O(N) skewed)
O(1) Zero heap allocations
O(1) Returns integer tree depth
Boundary Best / Worst Cases
time with stack on balanced tree.
time with stack.
time with stack on skewed tree (linked list shape).
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.
A null child must return COVERED (never NEEDS_CAMERA), otherwise every leaf's parent is forced into an unnecessary camera. The root has no parent to rely on: if dfs(root) returns NEEDS_CAMERA, one final camera must be added after the traversal.
Core Algorithmic State Invariants
Each recursive invocation evaluates disjoint subtrees independently, synthesizing solutions bottom-up from child return values without cross-branch interference.
Node state is computed from child results (e.g. 1 + max(L, R) for height, or sentinel -1 when balanced condition |L - R| <= 1 fails), bubbling answers toward the root.
Null nodes return mathematical identity values (0 for height/count, True for balance, None for LCA), guaranteeing clean recursion termination in O(H) stack space.
Binary Tree Cameras (LeetCode 968)
Postorder Greedy Tri-State Covering: Cameras Placed As Low As Possible
You are given the root of a binary tree. We install cameras on the tree nodes where 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.
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
Why It Works & Core Invariant
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
Establish initial problem boundaries and state invariants such that the valid search space is fully bounded.
lo, hi = 0, len(items) - 1| 1 | if not node: return COVERED |
| 2 | left_state, right_state = dfs(node.left), dfs(node.right) |
| 3 | if left_state == NEEDS_CAMERA or right_state == NEEDS_CAMERA: |
| 4 | cameras += 1; return HAS_CAMERA |
| 5 | if left_state == HAS_CAMERA or right_state == HAS_CAMERA: return COVERED |
| 6 | return NEEDS_CAMERA |
Target: Binary Tree Cameras (LeetCode 968). An absent child never forces a camera -- it is trivially covered
Subtree bottom-up aggregation: a node combines child subtree solutions upon backtrack; top-down invariants pass accumulated state down the path.
Base case: if not node: return base; recursive calls on left/right child nodes.
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.
🪄 Breaking Down the Code's "Magic Trick"
NEEDS_CAMERA, HAS_CAMERA, COVERED = 0, 1, 2 def dfs(node): if not node: return COVERED # an absent child can never demand a camera left, right = dfs(node.left), dfs(node.right) if left == NEEDS_CAMERA or right == NEEDS_CAMERA: cameras[0] += 1 return HAS_CAMERA # place greedily, as low as possible if left == HAS_CAMERA or right == HAS_CAMERA: return COVERED # a neighboring camera already sees this node return NEEDS_CAMERA # covered nowhere -- let the parent decide 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.
💡 Summary
When a tree problem's decision at one node depends only on a small, enumerable set of statuses reported by its children (not raw values), model the return value as a tri-state (or n-state) code and let each parent react greedily to exactly what its children report — this collapses what looks like a combinatorial covering problem into a single linear postorder pass.
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
You will see how a postorder tri-state code (uncovered / has-camera / covered) lets each parent greedily decide whether it must place a camera.
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
Placing a camera on every leaf: wasteful. A leaf's parent can cover it (and any siblings) with a single camera instead.
Returning NEEDS_CAMERA for a null child: forces every leaf's parent into an unnecessary camera. A null node must return COVERED.
Forgetting the root correction: the root has no parent to place a camera for it. If
dfs(root)returns NEEDS_CAMERA, one final camera must be added after the traversal.
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.
So: null returns COVERED; a NEEDS_CAMERA child forces the parent to place a camera (HAS_CAMERA); a HAS_CAMERA child naturally covers the parent (COVERED); otherwise the parent reports NEEDS_CAMERA upward.
Complexity & Mathematical Proof
O(N)
Look at the recursive function: `def maxDepth(node):`. For every node in the binary tree, the function executes exactly 2 recursive calls (`maxDepth(node.left)` and `maxDepth(node.right)`) and performs O(1) constant-time arithmetic combining their results (`1 + max(left, right)`). Because each of the N tree nodes is visited and processed exactly once, total time is N · O(1) = O(N).
O(H) Auxiliary
Look at the recursion call stack: Each recursive call adds a new stack frame storing the local `node` pointer. The maximum number of simultaneous stack frames alive at any instant equals the maximum path depth from root to leaf, which is the tree height H. In a balanced binary tree, H = log2(N) -> O(log N) stack memory. In a worst-case skewed tree (linked list), H = N -> O(N) stack memory. We allocate zero heap objects, so auxiliary space is bounded by tree height O(H).
T(N) = 2T(N/2) + O(1) ⟹ O(N)
Look at the recursive function: def maxDepth(node):. For every node in the binary tree, the function executes exactly 2 recursive calls (maxDepth(node.left) and maxDepth(node.right)) and performs O(1) constant-time arithmetic combining their results (1 + max(left, right)). Because each of the N tree nodes is visited and processed exactly once, total time is N · O(1) = O(N).
Derivation Progression
N nodes visited
Every node in the binary tree is entered and exited exactly once.
1 + max(left, right)
Combining child subproblem depths requires a single addition and max comparison in O(1).
T(N) = 2T(N/2) + O(1) ⟹ O(N)
Visiting all N nodes with constant combining work yields strictly O(N) time.
Variable Definitions
Memory Architecture & Bounds
O(H) Recursion stack storing tree height H frames (O(log N) balanced, O(N) skewed)
O(1) Zero heap allocations
O(1) Returns integer tree depth
Boundary Best / Worst Cases
time with stack on balanced tree.
time with stack.
time with stack on skewed tree (linked list shape).
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.
A null child must return COVERED (never NEEDS_CAMERA), otherwise every leaf's parent is forced into an unnecessary camera. The root has no parent to rely on: if dfs(root) returns NEEDS_CAMERA, one final camera must be added after the traversal.
Core Algorithmic State Invariants
Each recursive invocation evaluates disjoint subtrees independently, synthesizing solutions bottom-up from child return values without cross-branch interference.
Node state is computed from child results (e.g. 1 + max(L, R) for height, or sentinel -1 when balanced condition |L - R| <= 1 fails), bubbling answers toward the root.
Null nodes return mathematical identity values (0 for height/count, True for balance, None for LCA), guaranteeing clean recursion termination in O(H) stack space.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| if node is None: return COVERED | if not node: return COVERED | An absent child never forces a camera -- it is trivially covered |
| left_state, right_state = dfs_tri_state(node.left, ...), dfs_tri_state(node.right, ...) | left_state, right_state = dfs(node.left), dfs(node.right) | Postorder: both children must report their status before the parent can react |
| if left_state == NEEDS_CAMERA or right_state == NEEDS_CAMERA: cameras[0] += 1; return HAS_CAMERA | if left_state == NEEDS_CAMERA or right_state == NEEDS_CAMERA: cameras += 1; return HAS_CAMERA | Greedy placement: a camera is added as low in the tree as possible, only when truly forced |