968. Binary Tree Cameras - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Given the root of a binary tree, we want to install cameras on some of the tree’s nodes such that every node is monitored. Each camera at a node can monitor its parent, itself, and its immediate children. We need to determine the minimum number of cameras required to monitor all nodes in the tree.

Output: An integer representing the minimum number of cameras needed.

Example 1:
Input: [0,0,null,0,0]
Output: 1
Explanation: We can place one camera at the node with value 0 that is the left child of the root. This single camera covers its parent (the root), itself, and its two children, thus monitoring all nodes.

<small>Tree structure for Example 1:</small>

      0   <-- (Root)
     / 
    0   <-- (Camera here covers root, itself, and its children)
   / \
  0   0

All nodes in this tree are covered by the single camera as shown above.

Example 2:
Input: [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: In this tree, at least two cameras are needed to cover all nodes. One optimal configuration is to place one camera at a certain left child in the lower part of the tree and another camera at a right child, so that their coverage overlaps and all nodes become monitored. (Each camera monitors its node, its parent, and its immediate children.)

<small>Tree structure for Example 2 (one optimal camera placement):</small>

        0   <-- Root (covered by camera at right child)
       / \
      0   0
       \   \
        0   0
       /
      0   <-- Camera here covers its parent and left subtree

In this configuration, one camera on the left subtree covers the left side (its parent and left leaf), and another camera on the right child of the root covers the root and right side. No other placement can cover all nodes with fewer than 2 cameras.

Constraints: The tree has at least 1 node and at most 1000 nodes. Every node’s value is 0 (the values are irrelevant; only the tree structure matters).

Hints

Bottom-Up (Leaf-to-Root) Strategy: A key insight is to start placing cameras from the bottom (leaf level) upward rather than top-down. Placing a camera on a leaf node is wasteful because it only monitors its parent and itself (no children below). Instead, if a leaf node is not covered by any camera, we should place a camera on its parent. This way, the camera covers the parent, that leaf, and possibly the parent’s other child as well. By covering multiple nodes with one camera, we minimize the total count.
Greedy Coverage: We want to ensure all nodes are covered while using the fewest cameras. A greedy approach emerges: place cameras at nodes that are just above uncovered leaves. If a child node is uncovered, putting a camera at its parent covers the child, the parent, and other adjacent nodes. Conversely, if a child already has a camera, the parent is covered and doesn’t need its own camera. If all children of a node are covered (and none has a camera), that node itself becomes the only uncovered part, signaling that its parent should eventually get a camera. This forms a natural greedy rule: cover a node’s children first, then decide on the node.
Use of States (Dynamic Thinking): It helps to think of each node in terms of states or conditions after coverage decisions for its children are made:
- State 0: This node has no camera, but is covered by one of its children (or its parent). (In other words, it’s monitored without having a camera on it.)
- State 1: This node has a camera installed on it.
- State 2: This node is uncovered and needs coverage from its parent’s camera.
  These states guide the decision-making. For instance, if any child is in State 2 (needs coverage), the current node must be in State 1 (place a camera here) to cover that child. If any child is State 1 (has a camera), then the current node is already covered (State 0) by that child’s camera. If all children are State 0 (covered but without cameras), then they didn’t place a camera and also don’t need one from the current node, so the current node ends up in State 2 (uncovered, pushing the responsibility up to its parent).
Post-Order Traversal: The above strategy implies a post-order traversal (DFS) of the tree: compute the state of children first, then determine the state of the current node. This way, you know whether children are covered or not before deciding to place a camera at the current node. This bottom-up recursion naturally implements the greedy strategy while ensuring optimal coverage.

Multiple Approaches

Let’s discuss different approaches, from a brute-force idea to optimized strategies using greedy algorithms and dynamic programming on trees:

1. Brute-Force / Exhaustive Search

A brute-force approach would involve trying every possible combination of camera placements on nodes and checking if all nodes are covered. Essentially, for each node, decide to place a camera or not, and then verify coverage. This is equivalent to examining all subsets of nodes as potential camera locations. While conceptually straightforward, this approach is extremely inefficient – for a tree of N nodes, there are 2^N possible subsets of camera placements. Even with pruning (like skipping obviously redundant placements), the search space grows exponentially. For N up to 1000, brute-force is completely infeasible.

Why brute-force is impractical: The problem of selecting nodes to cover a tree optimally is analogous to the NP-hard “minimum vertex cover” problem in general graphs. Although a tree’s structure allows a polynomial solution, blindly trying all combinations doesn’t leverage the tree constraints and will time out for even moderate N. Hence, we need more clever strategies.

(Brute-force is more of a theoretical baseline here; in practice, we move directly to greedy or DP methods.)

2. Greedy DFS (Optimal Solution)

A well-known efficient solution uses a greedy, recursive DFS approach. The idea is as outlined in the hints: use a post-order traversal and decide greedily where to place cameras. This approach yields the minimum number of cameras needed.

Algorithm (Greedy DFS):

Traverse Post-Order: Perform a DFS that evaluates children before the current node.
Use States: For each node, determine one of three states after inspecting its children:
- Has Camera (install here) – We place a camera at this node. (This covers the node, its parent, and its children.)
- Covered (no camera) – This node is covered by a camera from one of its children (or, in general, it’s monitored by someone else).
- Needs Coverage – This node is not covered by any camera in its children, and it has no camera itself, so it will need its parent to cover it.
Decision Rules:
- If any child needs coverage (child state == “needs coverage”), then place a camera at the current node. This satisfies that child and covers the current node as well. Mark current node as “has camera” and increment the camera count.
- Else if any child has a camera, then the current node is already covered. Mark it as “covered” (no camera here).
- Otherwise (all children are covered and none has a camera), mark this node as “needs coverage” – it’s not covered, and we didn’t place a camera, so the responsibility is pushed up to the parent.
Handle Root: After DFS, if the root node ends up in the “needs coverage” state (meaning even the root wasn’t covered by any child’s camera), then place a camera at the root. This step ensures the root (and thus entire tree) is covered.

Using these rules, cameras are placed greedily where needed, and every camera placement is necessary for an uncovered child. This strategy has been proven to give an optimal (minimum) count of cameras for tree coverage. The greediness works here because whenever we decide to place a camera, it’s forced by an uncovered child – there’s no better alternative at that point.

Walk-through Example (Greedy DFS): Consider a simple chain of 3 nodes (a root, its child, and a grandchild). Starting from the leaf (grandchild): it has no children, so it’s uncovered (needs coverage). This causes its parent to place a camera. That parent now has a camera, which covers itself and the grandchild. The root (parent of the camera node) sees that its child has a camera, so the root is covered without needing its own camera. The root ends up covered and not needing a camera. The algorithm would place 1 camera (at the middle node), which is indeed the minimum to cover all three nodes.

This greedy DFS approach can be implemented cleanly with recursion (see code below). Each node’s return value or state informs its parent of what action (if any) is needed.

3. Dynamic Programming on Trees

Another approach is to use dynamic programming (DP) on the tree. We define subproblem states for each node that capture the cost (minimum cameras) under certain conditions. A common DP formulation uses three states similar to the ones described above:

State A (camera on this node): The minimum number of cameras needed for the subtree rooted at this node if we put a camera at this node.
State B (covered, no camera on this node): The minimum cameras needed for this subtree if this node is covered (monitored) but does NOT have a camera on it (meaning it must be covered by one of its children’s cameras).
State C (not covered): The minimum cameras for the subtree if this node is not covered yet (we allow this node to be uncovered, with the expectation that its parent will cover it).

Using these definitions, we can derive recurrence relations for a node based on its children:

State A (camera here): If we place a camera at this node, we add 1 to the count. This camera will cover this node and its immediate children, so the children can each be in either covered or not-covered state freely, as long as their subtrees are internally monitored. In other words, for each child we can take the minimum cost of either putting a camera there or not (States A, B, or C for the child), since even if the child ends up not covered (State C), our camera here will cover that child. However, to ensure minimality, if a child can manage with being not covered (State C) instead of covered (State B) and that yields fewer cameras, that’s acceptable because the camera at the current node covers the child. We choose the minimal combination for each child. Summing these up for all children and adding 1 for the current camera gives the cost for State A.
State B (covered, no camera here): If the current node has no camera but is covered, it means at least one of its children must have a camera to cover this node. We must cover both children’s subtrees fully as well (each child must be either have a camera or be covered). For each child, we can choose either State A (child has camera) or State B (child is covered without camera) – but not State C, because if a child were not covered (State C), then that child would be expecting this node to cover it, and since we are not placing a camera here in State B, that child would remain uncovered. So each child must be in a state that ensures the child’s subtree is fully covered (camera on child or child covered by its kids). Among the combinations of children states, we choose the minimum total cameras. Additionally, we have to ensure that at least one child is in State A (has a camera) to cover the current node. In practice, this means when computing combinations we should exclude the scenario where all children are just covered without cameras (State B for all), because then the current node wouldn’t be covered by any camera.
State C (not covered): In this scenario, the current node is not covered and has no camera, which means we are deferring coverage to this node’s parent. For the current node’s children, we simply need to cover their subtrees fully (because the current node being uncovered doesn’t directly affect the requirement for children). Each child can be either in State A or State B (camera or covered) – they just need to ensure their own coverage; we don’t require a child to cover the current node (that’s the parent’s job). Essentially, for each child we take the minimal cost of covering its subtree (either with or without a camera on that child), i.e. the minimum of State A or State B for the child. We sum these costs for all children. We do not allow children to be in State C in this case, because that would imply grandchildren covering the child while the current node is also uncovered – this could leave a gap where the current node and that child are both uncovered with no camera between them.

Once we compute these states for a node from its children, the answer for that node’s subtree can be derived. At the root, we cannot leave it uncovered (there’s no parent to cover it), so the final answer for the whole tree would be min(State A, State B) for the root. (Either we put a camera at the root or it is covered by a child’s camera – whichever yields fewer cameras.)

This DP approach is essentially a more formal way to reason about the greedy solution. It systematically tries combinations of placing cameras at children or not, ensuring coverage constraints, and takes minimums. It guarantees an optimal solution and runs in linear time on the tree. However, it’s more complex to implement and reason about than the greedy DFS, which is why the greedy approach is often preferred in interviews for its simplicity.

Note: The greedy DFS approach described earlier is effectively doing this DP implicitly. Each return state in the DFS corresponds to these DP states (with some inverted meaning, depending on implementation). Both methods achieve the same result with equal efficiency. The DP can be implemented either top-down with memoization or bottom-up via post-order traversal.

Code Implementations

Python Solution

Python3

. . . .

Explanation: The dfs function returns the state of each node:

0 if the node is covered (no camera at this node).
1 if there is a camera at this node.
2 if the node is not covered and needs a camera from its parent.

We use a cameras counter to count cameras placed. The logic in dfs follows the greedy rules:

If a child needs coverage (== 2), we place a camera at the current node (cameras += 1 and return state 1).
Else if any child has a camera (== 1), the current node is covered, so we return 0 (covered, no camera here).
Otherwise, the children are either covered or non-existent, and have no cameras, so the current node ends up needing coverage (return 2).

After traversal, if the root needs coverage, we increment the camera count for the root. This covers the case where the root itself had no camera and wasn’t covered by any child (for example, a tree of height 1, or a configuration where the root had no camera but also no children with cameras).

Java Solution

Java

. . . .

(In this Java implementation, we used 0 to indicate “needs coverage” for clarity, and 2 to indicate “covered, no camera.” The logic is analogous to the Python version.)

Both implementations run a single DFS traversal of the tree. During this traversal, cameras are counted and placed according to the greedy criteria. The code ensures that all nodes are covered by the end and that the number of cameras is minimal.

Complexity Analysis

Time Complexity: Both the greedy DFS and the DP-on-trees approaches run in linear time relative to the number of nodes. We visit each node once, doing O(1) work (determining states or computing DP values) per node. Thus, the time complexity is O(N) for a tree with N nodes. Brute-force, by contrast, would be O(2^N) in the worst case (exponential), which is infeasible for large N.
Space Complexity: The main extra space used is the recursion stack during DFS. In the worst case (a completely skewed tree), the recursion depth is N, so the space complexity is O(N). In a balanced tree, the depth is O(log N), making space usage about O(log N). No significant additional data structures are used beyond a few integers or state values. (If one used an explicit DP table or dictionary, it would hold at most 3 values per node, which is O(N) space as well.) The in-place state tracking in recursion is memory-efficient.
Optimality: It’s worth noting that these linear-time solutions leverage the tree structure. The problem, in general (for arbitrary graphs), is NP-hard, but for trees we achieve linear time with greedy/DP. The provided solution is optimal in both runtime and the number of cameras used.

Common Mistakes & Edge Cases

Common Mistakes:

Placing cameras on leaves: A frequent incorrect approach is to put cameras on leaf nodes to cover them. This is not optimal because a camera on a leaf only covers the leaf and its parent, whereas a camera on the parent covers the parent, the leaf, and potentially another child. Always try to cover a leaf by placing a camera on its parent instead.
Top-down greedy placement: Some might attempt to always place a camera at the root or higher-level nodes first. This can lead to suboptimal results. For example, placing a camera at the root too early might cover the root and its children, but you might end up needing additional cameras deeper in the tree that could have covered the root anyway. A bottom-up strategy is required for optimality – ensure your algorithm examines children before deciding for the parent.
Forgetting to cover the root: If using the DFS approach, one easy mistake is forgetting the final step of checking if the root is uncovered. If the root comes back as needing coverage and we don’t add a camera, the root (and thus the whole tree) won’t be fully monitored. Always handle the root after the DFS – if it’s not covered, add one more camera.
Misinterpreting states: When implementing, it’s easy to mix up what each return state represents. Clearly define the meaning of each state value (e.g., in our solution, we used a scheme where a returned value signals the node’s status to its parent). A wrong interpretation (such as treating None as uncovered instead of covered) can break the logic. Include comments or use an enum/named constants to avoid confusion.
Double counting cameras: Ensure that you only increment the camera counter when you actually place a camera. In the DFS approach, this happens exactly when a node finds an uncovered child and decides to install a camera. Don’t increment in any other case. Some implementations accidentally add cameras in multiple places (for example, both in the DFS and after it for root without checking state properly), leading to an incorrect count.
Not covering a child properly in DP: In the DP approach, a common pitfall is allowing an uncovered state where both a node and its child are uncovered. Make sure your DP transitions enforce that if a node is not placing a camera, its children must cover it (or the parent will). Any state combination that leaves a gap in coverage is invalid and should be excluded in the DP recursion or transition logic.

Edge Cases:

Single Node Tree: If the tree has only one node (the root), the answer must be 1. The root isn’t covered by anything else, so we need a camera on it. (Our DFS handles this: the root will be marked “needs coverage” and then we add a camera at the end.)
Empty Tree: This is not allowed by problem constraints (there is at least one node), but conceptually an empty tree would need 0 cameras. Our code would handle it by immediately returning 0, since the DFS on None returns covered.
Linear Tree (chain): For a skewed tree where each node has only one child (like a linked list), the optimal solution is to place cameras in an alternating fashion. For example, in a chain of 3 nodes, one camera in the middle covers all. In a chain of 4 nodes, two cameras are needed (one at the parent of the bottom leaf, and one at the root or the parent of root’s only child, depending on parity). The DFS strategy correctly handles this by effectively placing cameras on every other node. It’s good to mentally verify this scenario, as it tests the recursion logic thoroughly.
Full/Complete Tree: In a balanced tree, the greedy solution will place cameras roughly at every other level (covering two levels with one camera). This tends to result in covering all leaves with cameras at their parents, and so on up the tree. It’s a good stress test to ensure that no extra cameras are placed unnecessarily.
Tree with only two levels: (One root and some children, no grandchildren.) The optimal answer here is to put cameras at each child (covering the children and the root) or just put one at the root, depending on the number of children:
- If root has 1 child, one camera at the child is sufficient (covers root and child).
- If root has 2 children, one camera at the root covers all three nodes, which is optimal. The greedy algorithm as implemented will actually place cameras at each child (because each leaf child is uncovered, the parent root will place cameras at both? Let’s see: each leaf returns “needs coverage”, so root sees two children needing coverage and will place a camera on itself – actually, in our DFS logic, if either child needs coverage we place camera at the parent immediately. We don’t place two cameras, one for each child; the code places one camera at the root and returns “has camera”. That covers both children at once. So it handles it optimally.)
- This example underscores that the algorithm doesn’t double-place cameras – it addresses multiple uncovered children with one parent camera.
Random Structure: It’s worth considering a tree where some branches are deeper than others. The algorithm should independently handle each branch optimally and not be thrown off by the imbalance. Each subtree’s coverage is decided locally and bubbles up. This modularity is why the DFS solution works for any shape of tree.

The Binary Tree Cameras problem is a combination of tree traversal and greedy/dynamic programming reasoning. To practice similar skills, you might want to try:

LeetCode 337. House Robber III: Another tree DP problem where you decide to “rob” (take value from) a node or not. It’s similar in that you can’t take a node’s value if you take its parent’s (analogous to not placing adjacent cameras). Solving it uses DFS with states or recursion with memo, which is a comparable technique to this problem’s DP aspect. It will strengthen your understanding of tree post-order strategies and stateful decisions.
LeetCode 979. Distribute Coins in Binary Tree: A problem that also uses a DFS post-order traversal to balance some quantity (coins) in a tree. While the goal is different (move coins between nodes with minimal moves), the solving approach involves sending information up from children to parent (somewhat like greedy decisions). It’s good practice for thinking in terms of “what information should a child provide to its parent” – a theme common with the camera placement problem.
Minimum Vertex Cover on a Tree (General concept): The camera placement problem is essentially a tree’s minimum vertex cover/dominating set problem in disguise. While not a single LeetCode problem by that name, understanding the classic algorithm for minimum vertex cover in a tree (often taught with DP: choose a node or not, etc.) can help reinforce the concepts used here. Many competitive programming problems cover this idea. It involves similar state definitions (take a node in the cover or not, and ensure coverage of edges) which map closely to placing cameras or not on tree nodes. Practicing this concept can solidify your ability to reduce tree problems to post-order state-based solutions.