Binary Tree Cameras

59.7k
0

Given the root of a binary tree, cameras may be installed on tree nodes.

A camera monitors the camera node, the direct parent, and the immediate children. Return the minimum number of cameras needed to monitor every node in the tree.

Example 1

Input: root = [0, 0, null, 0, 0]
Output: 1
Explanation: A camera on the left child of the root monitors the root, the camera node, and both leaf children.

Example 2

Input: root = [0]
Output: 1
Explanation: A single-node tree needs one camera on the root.

Brute Force Approach

For a small tree, we can try every possible set of camera locations and keep the smallest valid set. Each node has two choices: place a camera or leave it empty. Therefore, exploring all choices covers every possible camera placement.

For each complete placement, we check whether every node is covered by a camera on itself, its parent, or one of its children. The smallest valid placement becomes the answer. However, repeatedly checking the entire tree for every possible placement makes this approach impractical for large trees.

Algorithm

  • Create a list of all nodes along with their parent and child relationships, so every camera placement can be checked efficiently.

  • Set best to the number of nodes because placing a camera on every node is always a valid upper bound.

  • Explore both choices for every node: camera absent and camera present, because every possible camera placement corresponds to one decision path.

  • Stop exploring a branch when cameraCount >= best, because adding more cameras cannot improve the current best answer.

  • When all nodes have been assigned, mark every camera node, its parent, and its immediate children as covered.

  • Reject the placement if any node remains uncovered, because every node must be monitored.

  • Update best with the smaller camera count for every valid placement.

  • Return best after all useful camera-placement choices have been explored.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
// Creates one binary-tree node.
TreeNode(int value) {
val = value;
left = nullptr;
right = nullptr;
}
};
class Solution {
private:
vector<TreeNode*> nodes;
vector<int> parentIndex;
vector<int> leftIndex;
vector<int> rightIndex;
vector<int> cameraAt;
int best;
// Collects nodes and direct relation positions.
int collect(TreeNode* node, int parent) {
// A missing child has no list position.
if (node == nullptr) {
return -1;
}
int current = nodes.size();
// Matching positions keep all relations aligned.
nodes.push_back(node);
parentIndex.push_back(parent);
leftIndex.push_back(-1);
rightIndex.push_back(-1);
// Child positions support later coverage marking.
int leftChild = collect(node->left, current);
int rightChild = collect(node->right, current);
// Stored child positions complete node relations.
leftIndex[current] = leftChild;
rightIndex[current] = rightChild;
return current;
}
// Checks coverage for one complete placement.
bool allCovered() {
vector<int> covered(nodes.size(), 0);
// Every selected camera marks all reachable nodes.
for (int index = 0; index < nodes.size(); index++) {
// An absent camera adds no coverage.
if (cameraAt[index] == 0) {
continue;
}
covered[index] = 1;
// A valid parent receives camera coverage.
if (parentIndex[index] != -1) {
covered[parentIndex[index]] = 1;
}
// A valid left child receives camera coverage.
if (leftIndex[index] != -1) {
covered[leftIndex[index]] = 1;
}
// A valid right child receives camera coverage.
if (rightIndex[index] != -1) {
covered[rightIndex[index]] = 1;
}
}
// One uncovered node invalidates the placement.
for (int value : covered) {
// A zero mark exposes missing coverage.
if (value == 0) {
return false;
}
}
return true;
}
// Explores every useful camera placement.
void search(int index, int cameraCount) {
// A non-improving branch needs no more choices.
if (cameraCount >= best) {
return;
}
// A complete placement is ready for validation.
if (index == nodes.size()) {
// Valid coverage can improve the answer.
if (allCovered()) {
best = cameraCount;
}
return;
}
// The first branch leaves the node without a camera.
cameraAt[index] = 0;
search(index + 1, cameraCount);
// The second branch places a camera on the node.
cameraAt[index] = 1;
search(index + 1, cameraCount + 1);
// Resetting preserves the parent branch state.
cameraAt[index] = 0;
}
public:

Complexity Analysis

Time Complexity: O(N × 2N), where N is the number of nodes, because each node has two choices—place a camera or not—and validating a complete placement can require O(N) coverage work.

Space Complexity: O(N), because the node-relation, camera, and coverage arrays, along with the recursion stack, require linear auxiliary space.

Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.

Better Approach

Exhaustive search can recompute the same subtrees many times. Instead, for each subtree, we store the minimum camera cost for three possible states: the current node has a camera, the current node is covered without a camera, or the current node remains uncovered so its parent can cover it.

A postorder traversal computes these three costs after both child states are known. The root cannot remain uncovered because it has no parent, so the final answer is the smaller cost between placing a camera at the root and covering it through a child.

Algorithm

  • Perform a postorder DFS so both child cost triples are available before calculating the current node's costs.

  • Return [INF, 0, 0] for a null child because a camera cannot be placed on a missing node, while the no-camera states contribute 0.

  • Calculate withCamera as 1 plus the minimum valid cost from each child, because a camera at the current node covers both child roots.

  • Calculate coveredNoCamera by requiring at least one child to have a camera, because without a camera at the current node, a child camera is needed to cover it.

  • Calculate uncovered by allowing both children to remain covered or uncovered as required by the state, because the current node is intentionally left for its parent to cover.

  • Return all three costs to the parent so it can choose the minimum compatible state without recomputing the subtree.

  • For the root, return min(withCamera, coveredNoCamera) because the root cannot remain uncovered.

  • Return the minimum root cost as the answer.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
// Creates one binary-tree node.
TreeNode(int value) {
val = value;
left = nullptr;
right = nullptr;
}
};
class Solution {
private:
int impossible = 1000000;
// Returns three minimum costs for one subtree.
vector<int> solve(TreeNode* node) {
// Missing space cannot contain a camera.
if (node == nullptr) {
return {impossible, 0, 0};
}
// Postorder supplies both child cost triples.
vector<int> left = solve(node->left);
vector<int> right = solve(node->right);
// A local camera permits every child state.
int withCamera =
1 + min({left[0], left[1], left[2]})
+ min({right[0], right[1], right[2]});
// At least one child camera covers the node.
int coveredByLeft =
left[0] + min(right[0], right[1]);
int coveredByRight =
right[0] + min(left[0], left[1]);
int coveredNoCamera =
min(coveredByLeft, coveredByRight);
// Covered camera-free children leave a gap above.
int uncovered = left[1] + right[1];
return {withCamera, coveredNoCamera, uncovered};
}
public:
// Returns the minimum camera count from root costs.
int minCameraCover(TreeNode* root) {
vector<int> answer = solve(root);
// A root cannot use the uncovered state.
return min(answer[0], answer[1]);
}
};
// Driver code
int main() {
TreeNode* root = new TreeNode(0);
root->left = new TreeNode(0);
root->left->left = new TreeNode(0);
root->left->right = new TreeNode(0);
Solution obj;
cout << obj.minCameraCover(root);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of nodes, because the postorder traversal visits each node once and performs constant work to compute the three state costs.

Space Complexity: O(H), where H is the height of the tree, because the recursion stack stores one constant-size cost triple for each active tree level.

Optimal Approach

The key observation is that we do not need to compare multiple costs at every node. A camera is needed at a node only when one of its children is uncovered. By processing the tree from the bottom up, we can place each camera as high as possible while still covering the uncovered child.

Postorder traversal lets us determine the state of both children before deciding the state of their parent. Each node reports one of three states: NEEDS_CAMERA, HAS_CAMERA, or COVERED. This allows every camera placement to be made only when necessary.

Algorithm

  • Perform a postorder DFS because the state of a node depends on the finalized states of both children.

  • Treat a null child as COVERED because it does not need monitoring and should not force a camera.

  • Return NEEDS_CAMERA when both children are COVERED, because neither child has a camera to cover the current node.

  • Place a camera and return HAS_CAMERA when either child is NEEDS_CAMERA, because the current node is the lowest position that can cover that uncovered child.

  • Return COVERED when either child has a camera, because that camera already covers the current node.

  • After the DFS, check the root. If it is NEEDS_CAMERA, add one more camera because the root has no parent to cover it.

  • Return the total camera count because every camera is placed only when required by an uncovered child.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
// Creates one binary-tree node.
TreeNode(int value) {
val = value;
left = nullptr;
right = nullptr;
}
};
class Solution {
private:
int cameras;
int needsCamera = 0;
int hasCamera = 1;
int covered = 2;
// Returns the greedy state for one subtree.
int solve(TreeNode* node) {
// Missing space never needs a camera.
if (node == nullptr) {
return covered;
}
// Postorder resolves both child states first.
int leftState = solve(node->left);
int rightState = solve(node->right);
// An uncovered child forces a parent camera.
if (leftState == needsCamera
|| rightState == needsCamera) {
cameras++;
return hasCamera;
}
// A child camera already covers the node.
if (leftState == hasCamera
|| rightState == hasCamera) {
return covered;
}
// Covered children leave the node for a parent.
return needsCamera;
}
public:
// Returns the minimum greedy camera count.
int minCameraCover(TreeNode* root) {
cameras = 0;
int rootState = solve(root);
// An uncovered root needs one final camera.
if (rootState == needsCamera) {
cameras++;
}
return cameras;
}
};
// Driver code
int main() {
TreeNode* root = new TreeNode(0);
root->left = new TreeNode(0);
root->left->left = new TreeNode(0);
root->left->right = new TreeNode(0);
Solution obj;
cout << obj.minCameraCover(root);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of nodes, because the postorder traversal visits each node once and performs constant work at every node.

Space Complexity: O(H), where H is the height of the tree, because the recursion stack stores at most one active call for each tree level.

Interview follow-up Questions

No. A missing child is treated as COVERED during greedy traversal, so missing space never creates a camera requirement.

Dynamic Programming

Read Similar Blogs

Dynamic Programming

Print Longest Increasing Subsequence

Input: arr = [5, 1, 6, 2, 3, 4] Output: [1, 2, 3, 4] Explanation: The values at indices 1, 3, 4, 5 preserve the original order and form a strictly increasing subsequence of maximum length 4 . Input...

115.1k
Dynamic Programming

Best Time to Buy and Sell Stock IV: At Most K Transactions

Given an integer k and an array prices , prices[day] stores the stock price on a particular day. At most k transactions may be completed. One transaction contains one buy followed by one sell. A se...

50.8k
Dynamic Programming

Best Time to Buy and Sell Stock with Transaction Fee

Input: prices = [1, 3, 2, 8, 4, 9] , fee = 2 Output: 8 Explanation: Buying at 1 and selling at 8 earns 8 - 1 - 2 = 5 . Buying at 4 and selling at 9 earns 9 - 4 - 2 = 3 . The maximum total profit is...

65.7k
Comments0