🧠
Brute Force (Pure Recursion with All Combinations)
💡 This approach tries all possible ways to place cameras on nodes to cover the entire tree. It is extremely slow but helps understand the problem deeply by exploring all configurations.
Intuition
Try placing a camera or not at each node and recursively check if the entire tree is covered. Return the minimum cameras needed among all valid configurations.
Algorithm
- At each node, try placing a camera or not.
- Recursively check if the subtree is covered with that choice.
- Combine results from left and right subtrees.
- Return the minimum cameras needed to cover the entire tree.
💡 The challenge is to check coverage and count cameras for every combination, which leads to exponential complexity.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def minCameraCover(root):
# Returns (covered, cameras) for subtree
def dfs(node, has_camera, parent_covered):
if not node:
return (True, 0) # Null nodes are covered without cameras
# Try placing camera here
left_cam = dfs(node.left, True, True)
right_cam = dfs(node.right, True, True)
cameras_with = 1 + left_cam[1] + right_cam[1]
# Try not placing camera here
left_no_cam = dfs(node.left, False, has_camera or parent_covered)
right_no_cam = dfs(node.right, False, has_camera or parent_covered)
if has_camera or parent_covered:
cameras_without = left_no_cam[1] + right_no_cam[1]
else:
cameras_without = float('inf')
if cameras_with < cameras_without:
return (True, cameras_with)
else:
return (has_camera or parent_covered, cameras_without)
covered, cameras = dfs(root, False, False)
return cameras
# Driver code
if __name__ == '__main__':
# Build example tree: [0,0,null,0,0]
root = TreeNode(0)
root.left = TreeNode(0)
root.left.left = TreeNode(0)
root.left.right = TreeNode(0)
print(minCameraCover(root)) # Expected output: 1
Line Notes
def dfs(node, has_camera, parent_covered):Defines recursive function with parameters to track camera placement and coverage
if not node:Base case: null nodes are considered covered without cameras
left_cam = dfs(node.left, True, True)Try placing a camera at current node, so children are covered
cameras_with = 1 + left_cam[1] + right_cam[1]Count cameras if placing camera here
if has_camera or parent_covered:If current node is covered by parent or has camera, no camera needed here
return camerasReturn minimum cameras needed for entire tree
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
public int minCameraCover(TreeNode root) {
int[] res = dfs(root, false, false);
return res[1];
}
// returns {covered (0 or 1), cameras}
private int[] dfs(TreeNode node, boolean hasCamera, boolean parentCovered) {
if (node == null) return new int[]{1, 0};
int[] leftWithCam = dfs(node.left, true, true);
int[] rightWithCam = dfs(node.right, true, true);
int camerasWith = 1 + leftWithCam[1] + rightWithCam[1];
int[] leftNoCam = dfs(node.left, false, hasCamera || parentCovered);
int[] rightNoCam = dfs(node.right, false, hasCamera || parentCovered);
int camerasWithout = (hasCamera || parentCovered) ? leftNoCam[1] + rightNoCam[1] : Integer.MAX_VALUE;
if (camerasWith < camerasWithout) return new int[]{1, camerasWith};
else return new int[]{(hasCamera || parentCovered) ? 1 : 0, camerasWithout};
}
public static void main(String[] args) {
TreeNode root = new TreeNode(0);
root.left = new TreeNode(0);
root.left.left = new TreeNode(0);
root.left.right = new TreeNode(0);
Solution sol = new Solution();
System.out.println(sol.minCameraCover(root)); // Expected: 1
}
}
Line Notes
private int[] dfs(TreeNode node, boolean hasCamera, boolean parentCovered)Recursive helper with camera and coverage flags
if (node == null) return new int[]{1, 0};Null nodes are covered with zero cameras
int camerasWith = 1 + leftWithCam[1] + rightWithCam[1];Count cameras if placing camera here
int camerasWithout = (hasCamera || parentCovered) ? ...Calculate cameras if not placing camera here but node covered
return new int[]{1, camerasWith};Return coverage and camera count for placing camera
#include <iostream>
#include <climits>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
pair<bool,int> dfs(TreeNode* node, bool hasCamera, bool parentCovered) {
if (!node) return {true, 0};
auto leftWithCam = dfs(node->left, true, true);
auto rightWithCam = dfs(node->right, true, true);
int camerasWith = 1 + leftWithCam.second + rightWithCam.second;
auto leftNoCam = dfs(node->left, false, hasCamera || parentCovered);
auto rightNoCam = dfs(node->right, false, hasCamera || parentCovered);
int camerasWithout = (hasCamera || parentCovered) ? leftNoCam.second + rightNoCam.second : INT_MAX;
if (camerasWith < camerasWithout) return {true, camerasWith};
else return {hasCamera || parentCovered, camerasWithout};
}
int minCameraCover(TreeNode* root) {
auto res = dfs(root, false, false);
return res.second;
}
int main() {
TreeNode* root = new TreeNode(0);
root->left = new TreeNode(0);
root->left->left = new TreeNode(0);
root->left->right = new TreeNode(0);
cout << minCameraCover(root) << endl; // Expected: 1
return 0;
}
Line Notes
pair<bool,int> dfs(TreeNode* node, bool hasCamera, bool parentCovered)Recursive function with coverage and camera flags
if (!node) return {true, 0};Null nodes are covered with zero cameras
int camerasWith = 1 + leftWithCam.second + rightWithCam.second;Count cameras if placing camera here
int camerasWithout = (hasCamera || parentCovered) ? ...Calculate cameras if not placing camera here but node covered
return res.second;Return minimum cameras needed for entire tree
function TreeNode(val, left=null, right=null) {
this.val = val;
this.left = left;
this.right = right;
}
function minCameraCover(root) {
function dfs(node, hasCamera, parentCovered) {
if (!node) return [true, 0];
let leftWithCam = dfs(node.left, true, true);
let rightWithCam = dfs(node.right, true, true);
let camerasWith = 1 + leftWithCam[1] + rightWithCam[1];
let leftNoCam = dfs(node.left, false, hasCamera || parentCovered);
let rightNoCam = dfs(node.right, false, hasCamera || parentCovered);
let camerasWithout = (hasCamera || parentCovered) ? leftNoCam[1] + rightNoCam[1] : Infinity;
if (camerasWith < camerasWithout) return [true, camerasWith];
else return [hasCamera || parentCovered, camerasWithout];
}
let res = dfs(root, false, false);
return res[1];
}
// Driver code
let root = new TreeNode(0);
root.left = new TreeNode(0);
root.left.left = new TreeNode(0);
root.left.right = new TreeNode(0);
console.log(minCameraCover(root)); // Expected: 1
Line Notes
function dfs(node, hasCamera, parentCovered)Recursive helper with camera and coverage flags
if (!node) return [true, 0];Null nodes are covered with zero cameras
let camerasWith = 1 + leftWithCam[1] + rightWithCam[1];Count cameras if placing camera here
let camerasWithout = (hasCamera || parentCovered) ? ...Calculate cameras if not placing camera here but node covered
return res[1];Return minimum cameras needed for entire tree
At each node, two choices (place camera or not) lead to exponential combinations. The recursion stack can go up to tree height.
💡 For n=20 nodes, this means over a million combinations, which is impractical.
Interview Verdict: TLE
This approach is too slow for large trees but helps understand the problem and motivates optimization.