Binary Tree Cameras - Video Solutions

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.