Log inSign up
hardleetcodeNot Started

Binary Tree Cameras

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

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.

Example 1 · Example 1: 5-Node Tree:

Input: root = [0, 0, null, 0, 0] Tree: 0 / 0 / \ 0 0
Output: 1
Explanation: One camera placed on the middle node monitors all 4 nodes.

Example 2 · Example 2: Chain Tree:

Input: root = [0, 0, null, 0, null, 0, null, null, 0] Tree: 0 / 0 / 0 / 0
Output: 2
Explanation: Two cameras needed to monitor the chain of nodes.

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • Node.val == 0

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why greedy placement beats general DP for camera coverage.
  • Design a 3-state bottom-up transition system on trees.
  • Handle edge cases where root remains uncovered.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Minimum dominating set on a tree.
  • Camera monitors node, parent, and children.
  • Greedy tree DP / state machine.

Algorithmic Decision Tree:

  • If left == 0 || right == 0 -> cameras++, return 1.
  • If left == 1 || right == 1 -> return 2.
  • return 0.
  • If dfs(root) == 0 -> cameras++.

Connected Patterns:

House Robber IIIMinimum Vertex Cover in a TreeBinary Tree Maximum Path Sum

1. Classic Tree DP (3 States with Minimums)

Intuition

dp[node][0] = cost if camera placed at node. dp[node][1] = cost if covered by child. dp[node][2] = cost if covered by parent.

When to apply: Formal Dynamic Programming approach.

Algorithm

  1. Step 1: Helper dfs(node) returns tuple (d0, d1, d2).
  2. Step 2: Combine subtree states using min combinations.
  3. Step 3: Return min(d0, d1) for root.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 tuple<int, int, int> dfs(TreeNode* node) {
9 if (!node) return {10000, 0, 0};
10 auto [l0, l1, l2] = dfs(node->left);
11 auto [r0, r1, r2] = dfs(node->right);
12 int d0 = 1 + min({l0, l1, l2}) + min({r0, r1, r2});
13 int d1 = min({l0 + r0, l0 + r1, l1 + r0});
14 int d2 = min(l0, l1) + min(r0, r1);
15 return {d0, d1, d2};
16 }
17public:
18 int minCameraCover(TreeNode* root) {
19 auto [d0, d1, d2] = dfs(root);
20 return min(d0, d1);
21 }
22};
23
24int main() {
25 // Sample driver execution
26 cout << "Execution completed successfully." << endl;
27 return 0;
28}
29

Time & Space Complexity

  • Time complexity: O(n) — Computes 3 states per node in O(1).
  • Space complexity: O(h) — Call stack bounded by tree height h.

2. Greedy DFS with Set of Monitored Nodes

Intuition

Postorder DFS: if child not in set, place camera on node and add node, parent, and children to set.

When to apply: Set-based greedy simulation.

Algorithm

  1. Step 1: Set covered contains null.
  2. Step 2: dfs(node, parent): postorder visit.
  3. Step 3: If left not covered or right not covered: add node to cameras; add node, parent, left, right to covered.
  4. Step 4: If root not covered, cameras++.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 int cameras = 0;
9 unordered_set<TreeNode*> covered;
10 void dfs(TreeNode* node, TreeNode* parent) {
11 if (!node) return;
12 dfs(node->left, node);
13 dfs(node->right, node);
14 if ((!parent && !covered.count(node)) ||
15 (node->left && !covered.count(node->left)) ||
16 (node->right && !covered.count(node->right))) {
17 cameras++;
18 covered.insert(node);
19 covered.insert(parent);
20 covered.insert(node->left);
21 covered.insert(node->right);
22 }
23 }
24public:
25 int minCameraCover(TreeNode* root) {
26 covered.insert(nullptr);
27 dfs(root, nullptr);
28 return cameras;
29 }
30};
31
32int main() {
33 // Sample driver execution
34 cout << "Execution completed successfully." << endl;
35 return 0;
36}
37

Time & Space Complexity

  • Time complexity: O(n) — Set lookups take O(1); visits each node once.
  • Space complexity: O(n) — Set holds up to n nodes.

3. Greedy 3-State Bottom-Up DFS (Strict O(h) Space)

Intuition

0 = uncovered, 1 = has camera, 2 = covered. If either child is 0, place camera (cameras++, return 1). If either child is 1, return 2. Else return 0. If root returns 0, cameras++.

When to apply: Optimal gold-standard solution.

Algorithm

  1. Step 1: cameras = 0.
  2. Step 2: Helper dfs(node): if null return 2 (covered).
  3. Step 3: left = dfs(node.left); right = dfs(node.right).
  4. Step 4: If left == 0 || right == 0: cameras++; return 1.
  5. Step 5: If left == 1 || right == 1: return 2.
  6. Step 6: return 0. If dfs(root) == 0: cameras++. Return cameras.

Camera State Machine Trace for root = [0, 0, null, 0, 0]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Leaves (left and right) return state 0 (uncovered)
Visual state
Values and pointers at this exact step
tree
Root
0
L
0 (state 0)
R
0 (state 0)

Node order shown; add connections to display explicit tree edges.

uncovered: 0L
Check / comparison
Children are state 0 (uncovered)
Decision / next transition
Parent must place camera.
Why this step matters

Step 1: Leaves (left and right) return state 0 (uncovered).

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 int cameras = 0;
9 int dfs(TreeNode* root) {
10 if (!root) return 2;
11 int left = dfs(root->left);
12 int right = dfs(root->right);
13 if (left == 0 || right == 0) {
14 cameras++;
15 return 1;
16 }
17 if (left == 1 || right == 1) return 2;
18 return 0;
19 }
20public:
21 int minCameraCover(TreeNode* root) {
22 if (dfs(root) == 0) cameras++;
23 return cameras;
24 }
25};
26
27int main() {
28 // Sample driver execution
29 cout << "Execution completed successfully." << endl;
30 return 0;
31}
32

Time & Space Complexity

  • Time complexity: O(n) — Single traversal visiting each node once.
  • Space complexity: O(h) — Call stack bounded by tree height h.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Formal 3-State Tree DPO(n)O(h)Computes min costs for all 3 state possibilities.Multiple min comparisons.
2.Greedy DFS with Monitored SetO(n)O(n)Set stores all covered nodes.Set insertions.
3.Greedy 3-State Bottom-Up DFSOptimalO(n)O(h)Return state integer: 0 (uncovered), 1 (camera), 2 (covered).None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Single node tree: root needs camera -> returns 1.
  • 2-node tree: root places camera to cover child -> returns 1.
  • Linear chain of 3 nodes: middle node gets camera -> returns 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain why placing cameras bottom-up on parents of leaves is strictly better than placing on leaves (parent covers up to 3 neighbors vs leaf covering only 1).
  2. Remind the interviewer about the final check if (dfs(root) == 0) cameras++.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why are null nodes treated as State 2 (Covered) in the greedy bottom-up DFS?

Back to DSA Sheet