968. Binary Tree Cameras Solution

The problem

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:

Input: root = [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.

Example 2:

Input: root = [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

Constraints:

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

Approach overview

Problem Overview: You are given the root of a binary tree. Each camera placed on a node can monitor its parent, itself, and its immediate children. The goal is to place the minimum number of cameras so every node in the tree is covered.

Approach 1: Dynamic Programming with Memoization (O(n) time, O(n) space)

This method models the problem as a state-based decision at each node. For every node, you evaluate multiple states: placing a camera here, covering the node from its parent, or relying on children to cover it. The recursion explores combinations of these states while memoizing results for subtrees to avoid recomputation. Each state calculates the minimum cameras required given the coverage constraints, then combines results from left and right children. The idea works but introduces multiple state transitions per node, making the implementation heavier even though the complexity remains linear. This technique demonstrates classic tree DP patterns used in dynamic programming problems on trees.

Approach 2: Greedy Depth-First Search (DFS) (O(n) time, O(h) space)

The optimal approach uses a bottom-up DFS traversal and assigns one of three states to each node: 0 = not covered, 1 = has camera, 2 = covered. While returning from recursion, you inspect the states of the left and right children. If any child is not covered, you place a camera at the current node. If any child already has a camera, the current node becomes covered. Otherwise, the node remains uncovered and lets its parent handle coverage. This greedy rule works because cameras cover both parent and children, so placing them at the lowest necessary point maximizes coverage. The DFS processes each node once, making the algorithm efficient and clean. The traversal pattern follows standard depth-first search over a binary tree.

Recommended for interviews: The Greedy DFS solution is what interviewers usually expect. It shows you understand tree traversal and local decision strategies that produce a global optimum. Mentioning the DP formulation demonstrates deeper reasoning about state transitions, but implementing the greedy DFS with three states is the fastest and most elegant approach under interview pressure.

Approach 1: Greedy Depth-First Search (DFS)

The greedy DFS solution is based on a bottom-up approach. We classify each node into one of three states: covered by a camera, has a camera, or needs a camera. A node needs a camera if its children are not covered. We use a post-order DFS strategy to ensure all children are addressed before deciding the current node's state. The optimal way to cover a subtree is to place a camera on nodes whose children are not covered.

Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def minCameraCover(self, root: TreeNode) -> int:
        self.min_cameras = 0

        def dfs(node):
            if not node:
                return 2
            left = dfs(node.left)
            right = dfs(node.right)
            if left == 0 or right == 0:
                self.min_cameras += 1
                return 1
            return 2 if left == 1 or right == 1 else 0

        if dfs(root) == 0:
            self.min_cameras += 1
        return self.min_cameras

Java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() { this.val = 0; }
}

class Solution {
    int minCameras = 0;
    
    public int dfs(TreeNode node) {
        if (node == null) return 2;
        int left = dfs(node.left);
        int right = dfs(node.right);
        
        if (left == 0 || right == 0) {
            minCameras++;
            return 1;
        }
        return (left == 1 || right == 1) ? 2 : 0;
    }
    
    public int minCameraCover(TreeNode root) {
        if (dfs(root) == 0) minCameras++;
        return minCameras;
    }
}

C++

#include <iostream>
#include <algorithm>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int minCameras = 0;
    
    int dfs(TreeNode* node) {
        if (node == nullptr) return 2;
        int left = dfs(node->left);
        int right = dfs(node->right);
        
        if (left == 0 || right == 0) {
            minCameras++;
            return 1;
        }
        return (left == 1 || right == 1) ? 2 : 0;
    }
    
    int minCameraCover(TreeNode* root) {
        if (dfs(root) == 0) minCameras++;
        return minCameras;
    }
};

JavaScript

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

var minCameraCover = function(root) {
    let minCameras = 0;
    
    const dfs = function(node) {
        if (!node) return 2;
        let left = dfs(node.left);
        let right = dfs(node.right);
        if (left === 0 || right === 0) {
            minCameras++;
            return 1;
        }
        return (left === 1 || right === 1) ? 2 : 0;
    };
    
    if (dfs(root) === 0) minCameras++;
    return minCameras;
};

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

int minCameras;

int dfs(struct TreeNode* node) {
    if (!node) return 2; // if null, considered covered
    
    int left = dfs(node->left);
    int right = dfs(node->right);
    
    if (left == 0 || right == 0) {
        minCameras++;
        return 1; // install camera
    }
    return (left == 1 || right == 1) ? 2 : 0;
}

int minCameraCover(struct TreeNode* root) {
    minCameras = 0;
    return (dfs(root) == 0 ? 1 : 0) + minCameras;
}

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int value = 0) {
        val = value;
    }
}

public class Solution {
    private int minCameras = 0;
    
    public int MinCameraCover(TreeNode root) {
        if (DFS(root) == 0) minCameras++;
        return minCameras;
    }
    
    private int DFS(TreeNode node) {
        if (node == null) return 2;
        int left = DFS(node.left);
        int right = DFS(node.right);
        if (left == 0 || right == 0) {
            minCameras++;
            return 1;
        }
        return (left == 1 || right == 1) ? 2 : 0;
    }
}

The Python implementation uses recursion inside the DFS function to post-order traverse the tree. It increments `self.min_cameras` when a camera is needed because the node's children are not covered.

Complexity

Time Complexity: O(n), touching each node once.
Space Complexity: O(h) for the call stack, with h as the height of the tree.

Try this approach in the editor

Approach 2: Dynamic Programming with Memoization

This approach leverages dynamic programming through a recursive function with memoization to reduce redundant calculations. Each node can have three states represented in a tuple: it has a camera, it's covered but doesn't have a camera, or it's not covered. Using this state information, the solution calculates camera placements strategically.

Python

from functools import lru_cache

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def minCameraCover(self, root: TreeNode) -> int:
        @lru_cache(None)
        def dfs(node):
            if not node:
                return (0, 0, float('inf'))
            L = dfs(node.left)
            R = dfs(node.right)
            dp0 = L[1] + R[1] + 1
            dp1 = min(dp0, min(L[0] + R[1], L[1] + R[0]))
            dp2 = min(dp0, L[1] + R[1])
            return (dp0, dp1, dp2)
        return dfs(root)[1]

This solution uses dynamic programming with memoization to avoid redundant recursive calls. The function `dfs` returns a tuple of three states for each node: the cost of having a camera, being covered without a camera, and not being covered.
The first element, `dp0`, calculates cost when a camera is placed at the current node. The second, `dp1`, calculates when the node is covered without having a camera, and the third, `dp2`, calculates when the node itself isn't covered.

Complexity

Time Complexity: O(n), where n is the number of nodes.
Space Complexity: O(n), due to memoization storage.

Try this approach in the editor

Approach 3: Dynamic Programming (Tree DP)

For each node, we define three states:

a: The current node has a camera
b: The current node does not have a camera, but is monitored by its children
c: The current node does not have a camera and is not monitored by its children

Next, we design a function dfs(root), which will return an array of length 3, representing the minimum number of cameras in the subtree rooted at root for the three states. The answer is min(dfs(root)[0], dfs(root)[1]).

The calculation process of the function dfs(root) is as follows:

If root is null, return [inf, 0, 0], where inf represents a very large number, used to indicate an impossible situation.

Otherwise, we recursively calculate the left and right subtrees of root, obtaining [la, lb, lc] and [ra, rb, rc] respectively.

If the current node has a camera, then its left and right children must be in a monitored state, i.e., a = min(la, lb, lc) + min(ra, rb, rc) + 1.
If the current node does not have a camera but is monitored by its children, then one or both of the children must have a camera, i.e., b = min(la + rb, lb + ra, la + ra).
If the current node does not have a camera and is not monitored by its children, then the children must be monitored by their children, i.e., c = lb + rb.

Finally, we return [a, b, c].

The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes in the binary tree.

TypeScript

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function minCameraCover(root: TreeNode | null): number {
    const dfs = (root: TreeNode | null): number[] => {
        if (!root) {
            return [1 << 29, 0, 0];
        }
        const [la, lb, lc] = dfs(root.left);
        const [ra, rb, rc] = dfs(root.right);
        const a = 1 + Math.min(la, lb, lc) + Math.min(ra, rb, rc);
        const b = Math.min(la + ra, la + rb, lb + ra);
        const c = lb + rb;
        return [a, b, c];
    };
    const [a, b, _] = dfs(root);
    return Math.min(a, b);
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minCameraCover(root *TreeNode) int {
	var dfs func(*TreeNode) (int, int, int)
	dfs = func(root *TreeNode) (int, int, int) {
		if root == nil {
			return 1 << 29, 0, 0
		}
		la, lb, lc := dfs(root.Left)
		ra, rb, rc := dfs(root.Right)
		a := 1 + min(la, min(lb, lc)) + min(ra, min(rb, rc))
		b := min(la+ra, min(la+rb, lb+ra))
		c := lb + rb
		return a, b, c
	}
	a, b, _ := dfs(root)
	return min(a, b)
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Depth-First Search (DFS)	Time Complexity: O(n), touching each node once. Space Complexity: O(h) for the call stack, with h as the height of the tree.
Dynamic Programming with Memoization	Time Complexity: O(n), where n is the number of nodes. Space Complexity: O(n), due to memoization storage.
Dynamic Programming (Tree DP)	–

Complexity analysis

Approach	Time	Space	When to Use
Dynamic Programming with Memoization	O(n)	O(n)	When exploring explicit coverage states for each node or demonstrating tree DP reasoning
Greedy Depth-First Search (DFS)	O(n)	O(h)	Best practical solution; minimal cameras using a single postorder traversal

Frequently asked questions

Is Binary Tree Cameras easy or hard?

Binary Tree Cameras is categorized as a hard problem because it requires recognizing the correct greedy state transitions during DFS. Once the three-state model is understood, the implementation becomes relatively compact.

How to solve Binary Tree Cameras in O(n)?

Perform a postorder DFS and assign states to each node: 0 for not covered, 1 for a camera placed, and 2 for covered. If any child is uncovered, place a camera at the current node. If any child has a camera, the node becomes covered. Otherwise it remains uncovered so the parent can handle it.

Binary Tree Cameras Python or Java solution

Both Python and Java implementations follow the same DFS strategy. A recursive function returns the coverage state of each node and increments a camera counter when a camera must be placed. The algorithm processes every node once, giving O(n) time complexity.

What is the best approach for Binary Tree Cameras?

The greedy depth-first search approach is the most efficient and commonly expected solution. Each node returns one of three states: uncovered, covered, or has a camera. Cameras are placed only when a child is uncovered, which guarantees minimal placement. This solution runs in O(n) time and uses O(h) recursion space.

What data structure is used in Binary Tree Cameras?

The problem operates on a binary tree and is typically solved using depth-first search recursion. Some solutions also model the problem using dynamic programming states stored per node in the tree.

What is the time complexity of Binary Tree Cameras?

The optimal solution runs in O(n) time because every node in the binary tree is visited exactly once during the DFS traversal. The space complexity is O(h), where h is the height of the tree, due to recursion stack usage.

Is Binary Tree Cameras asked at Google Amazon or Meta?

Binary Tree Cameras is a classic tree greedy problem that appears in interview preparation lists for companies like Google, Amazon, and Meta. It tests understanding of DFS traversal, tree state management, and greedy placement strategies.

Binary Tree Cameras solution and explanation

The problem

Approach overview

Approach 1: Greedy Depth-First Search (DFS)

Approach 2: Dynamic Programming with Memoization

Approach 3: Dynamic Programming (Tree DP)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Binary Tree Cameras solution and explanation

The problem

Approach overview

Approach 1: Greedy Depth-First Search (DFS)

Approach 2: Dynamic Programming with Memoization

Approach 3: Dynamic Programming (Tree DP)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems