LeetCode 968 - Binary Tree Cameras

This problem asks us to determine the minimum number of cameras required to monitor all nodes in a binary tree. Each camera placed on a node can monitor its parent, itself, and its immediate children.

leetcodeharddynamic-programmingtreedepth-first-searchbinary-tree

LeetCode Problem 968

Difficulty: 🔴 Hard
Topics: Dynamic Programming, Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

This problem asks us to determine the minimum number of cameras required to monitor all nodes in a binary tree. Each camera placed on a node can monitor its parent, itself, and its immediate children. The input is the root of a binary tree, where each node has a value 0 and may have left and right children. The output is a single integer representing the minimum number of cameras needed to cover all nodes.

The constraints tell us that the tree can have up to 1000 nodes, which is small enough for a linear or slightly more-than-linear solution, but a purely brute-force recursive approach that explores all camera placements would be too slow. Important edge cases include a single-node tree (which always requires one camera), skewed trees that resemble a linked list, and trees where optimal camera placement is not on leaf nodes but slightly higher in the tree.

The challenge here is to find a systematic way to place cameras such that every node is monitored while minimizing the total number of cameras. Naively placing cameras at leaves or at every node would not be efficient.

Approaches

Brute Force

A brute-force approach would consider every node and decide recursively whether to place a camera there or not. For each node, we could attempt all combinations of camera placements for its children and sum the total cameras required. While this would eventually produce the correct result, the number of possible camera placements grows exponentially with the number of nodes, making it infeasible for n = 1000.

Optimal Approach

The key insight for an optimal solution is to use a greedy bottom-up approach via depth-first search and dynamic programming. For each node, we can classify its state as one of three:

  1. Has a camera - the node itself has a camera.
  2. Covered - the node does not have a camera but is monitored by its children or parent.
  3. Needs coverage - the node is not monitored by any camera.

By performing a post-order traversal, we decide the state of a node based on the states of its children. If any child needs coverage, we must place a camera at the current node. This ensures minimal cameras are placed, as cameras are placed only when necessary and cover multiple nodes whenever possible.

This approach guarantees an optimal solution because it greedily ensures each subtree is fully covered while avoiding redundant camera placements.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Explore all camera placements recursively, too slow
Optimal O(n) O(h) Post-order DFS, h is tree height, place camera only when children need coverage

Algorithm Walkthrough

  1. Perform a post-order depth-first traversal of the binary tree.
  2. For each node, check the state of its left and right children.
  3. If any child is in the "needs coverage" state, place a camera at the current node and mark it as "has a camera."
  4. If any child "has a camera," mark the current node as "covered."
  5. If both children are "covered" but do not have a camera, mark the current node as "needs coverage."
  6. After traversal, if the root itself is in "needs coverage," place one additional camera at the root.
  7. Count all cameras placed during traversal and return the total.

Why it works: The post-order traversal ensures that decisions are made from leaves up to the root, so a camera is placed at a node only when necessary to cover uncovered children. This guarantees minimal camera usage while ensuring full coverage.

Python Solution

# Definition for a binary tree node.
# 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: Optional[TreeNode]) -> int:
        HAS_CAMERA = 0
        COVERED = 1
        NEEDS_COVERAGE = 2

        self.camera_count = 0

        def dfs(node: Optional[TreeNode]) -> int:
            if not node:
                return COVERED

            left = dfs(node.left)
            right = dfs(node.right)

            if left == NEEDS_COVERAGE or right == NEEDS_COVERAGE:
                self.camera_count += 1
                return HAS_CAMERA
            if left == HAS_CAMERA or right == HAS_CAMERA:
                return COVERED
            return NEEDS_COVERAGE

        if dfs(root) == NEEDS_COVERAGE:
            self.camera_count += 1

        return self.camera_count

Implementation Explanation: The dfs function returns a state for each node. Leaf nodes return COVERED by default if they are None. If a node has a child that needs coverage, a camera is placed at that node. If a node has a child with a camera, the node itself is covered. Finally, after DFS, if the root still needs coverage, we add one more camera.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func minCameraCover(root *TreeNode) int {
    const (
        HAS_CAMERA = iota
        COVERED
        NEEDS_COVERAGE
    )

    cameraCount := 0

    var dfs func(node *TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return COVERED
        }

        left := dfs(node.Left)
        right := dfs(node.Right)

        if left == NEEDS_COVERAGE || right == NEEDS_COVERAGE {
            cameraCount++
            return HAS_CAMERA
        }
        if left == HAS_CAMERA || right == HAS_CAMERA {
            return COVERED
        }
        return NEEDS_COVERAGE
    }

    if dfs(root) == NEEDS_COVERAGE {
        cameraCount++
    }

    return cameraCount
}

Go-specific Notes: In Go, we use iota to define the state constants. nil is used for missing children. The recursion and state logic are identical to Python, and cameraCount is updated whenever a camera is placed.

Worked Examples

Example 1

Input: [0,0,null,0,0]

Post-order DFS:

Node Left State Right State Action Resulting State
Node 0 (leaf) N/A N/A None NEEDS_COVERAGE
Node 0 (parent of leaf) NEEDS_COVERAGE NEEDS_COVERAGE Place camera HAS_CAMERA
Root 0 HAS_CAMERA N/A Covered by child COVERED

Output: 1

Example 2

Input: [0,0,null,0,null,0,null,null,0]

DFS propagates camera placements up, resulting in 2 cameras placed at optimal nodes.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is visited once in post-order DFS
Space O(h) Recursion stack, h is tree height

The linear time complexity arises from the single traversal of the tree. Space complexity is proportional to the recursion depth, which is the height of the tree.

Test Cases

# Provided examples
assert Solution().minCameraCover(TreeNode(0, TreeNode(0, None, TreeNode(0, TreeNode(0))))) == 1  # Example 1
assert Solution().minCameraCover(TreeNode(0, TreeNode(0, None, TreeNode(0, None, TreeNode(0, None, TreeNode(0)))))) == 2  # Example 2

# Single node tree
assert Solution().minCameraCover(TreeNode(0)) == 1

# Skewed left tree
assert Solution().minCameraCover(TreeNode(0, TreeNode(0, TreeNode(0)))) == 1

# Skewed right tree
assert Solution().minCameraCover(TreeNode(0, None, TreeNode(0, None, TreeNode(0)))) == 1

# Complete binary tree of height 3
assert Solution().minCameraCover(
    TreeNode(0,
             TreeNode(0, TreeNode(0), TreeNode(0)),
             TreeNode(0, TreeNode(0), TreeNode(0))
    )) == 2
Test Why
Example 1 Validates basic tree with minimal camera placement
Example 2 Validates more complex tree needing multiple cameras
Single node Edge case: smallest tree
Skewed left/right Edge case: tree like linked list
Complete tree height 3 Validates optimal camera placement in full binary tree

Edge Cases

A key edge case is a single-node tree, where a camera is always required; the algorithm correctly detects this by checking if the root needs coverage after DFS. Another edge case is a completely skewed tree, which resembles a linked list; the algorithm places cameras optimally every two nodes to cover all nodes. A third edge case involves subtrees of different heights, where placing a camera only on the taller subtree may leave shorter subtrees uncovered; the bottom-up DFS ensures all children are checked before placing a camera, handling this correctly.