Course4all
Join us on telegram
Home/dsa/Trees/Binary Tree Cameras

Binary Tree Cameras

Master this topic with zero to advance depth.

Binary Tree Cameras

Min cameras.

Hard
Approach 1

Level I: BFS (Try all camera placements)

Intuition

A brute force approach would try every possible subset of nodes to place cameras and check if all nodes are covered. Since there are 2N2^N subsets, this is too slow but conceptually simple.

Logic

  1. Generate all 2N2^N combinations of camera placements.
  2. For each combination, check if all nodes are covered.
  3. Return the minimum size of a valid combination.
⏱ O(2^N * N)💾 O(N)

Detailed Dry Run

Try all 8 combinations for 3 nodes. Min cameras = 1 (at root).

java
public class Main {
    public int minCameraCover(TreeNode root) {
        Set<TreeNode> cameras = new HashSet<>();
        Set<TreeNode> covered = new HashSet<>();
        return solve(root, cameras, covered);
    }
    // Simplified brute force concept: try placing vs not placing.
    private int solve(TreeNode node, Set<TreeNode> cameras, Set<TreeNode> covered) {
        // ... Brute force implementation would be extremely long ...
        return 0; 
    }
}
Approach 2

Level II: Dynamic Programming (Recursive with 3 States)

Intuition

For each node, we can track 3 states:

  1. Node has a camera.
  2. Node is covered by a child.
  3. Node is not yet covered (must be covered by parent).

Logic

  • dp(node, state) returns min cameras for subtree rooted at node given state. This avoids the greedy assumptions by exploring all valid coverages recursiveley.
⏱ O(N)💾 O(H)

Detailed Dry Run

DP(root, hasCamera) returns min of children. DP(root, notCovered) forces parent camera.

java
public class Main {
    public int minCameraCover(TreeNode root) {
        int[] res = solve(root);
        return Math.min(res[1], res[2]);
    }
    private int[] solve(TreeNode node) {
        if (node == null) return new int[]{0, 0, 99999};
        int[] L = solve(node.left), R = solve(node.right);
        int d0 = L[1] + R[1];
        int d1 = Math.min(L[2] + Math.min(R[1], R[2]), R[2] + Math.min(L[1], L[2]));
        int d2 = 1 + Math.min(L[0], Math.min(L[1], L[2])) + Math.min(R[0], Math.min(R[1], R[2]));
        return new int[]{d0, d1, d2};
    }
}
Approach 3

Level III: Optimal (Greedy Post-Order)

Intuition

Thought Process

We want to place cameras such that we cover all nodes with the minimum number. A camera at a node covers itself, its parent, and its children.

Greedy Strategy: It's always better to place a camera at a parent of a leaf node rather than the leaf node itself. A camera at the parent covers more nodes.

Node States

  1. 0: Node is not covered.
  2. 1: Node has a camera.
  3. 2: Node is covered but has no camera.

Logic

  • If children are not covered (0), parent must have a camera (1).
  • If children have a camera (1), parent is covered (2).
  • Otherwise, node is not covered (0).
⏱ O(N)💾 O(H)

Detailed Dry Run

NodeLeft StateRight StateNode StateAction
Leaf220Return 0 (leaf uncovered)
Parent001Camera++ (covers leaf)
GrandP112Covered by child
java
public class Main {
    int count = 0;
    public int minCameraCover(TreeNode root) {
        return (dfs(root) == 0 ? 1 : 0) + count;
    }
    private int dfs(TreeNode node) {
        if (node == null) return 2;
        int left = dfs(node.left), right = dfs(node.right);
        if (left == 0 || right == 0) {
            count++;
            return 1;
        }
        return (left == 1 || right == 1) ? 2 : 0;
    }
}
← Previous QuestionPath Sum IV
Next Question →Find Duplicate Subtrees