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:
[1, 1000].Node.val == 0Problem 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.
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.
The code uses a post-order DFS traversal. It installs a camera at a node if either of its children need a camera (state 0). At the end, if the root itself needs a camera, we increment the count by one. Each node returns a state: 0 if it needs coverage, 1 if it has a camera, and 2 if it's covered.
Time Complexity: O(n), where n is the number of nodes in the tree, due to the DFS traversal of every node.
Space Complexity: O(h), where h is the height of the tree, due to the recursion stack space.
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.
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.
Python
Time Complexity: O(n), where n is the number of nodes.
Space Complexity: O(n), due to memoization storage.
For each node, we define three states:
a: The current node has a camerab: The current node does not have a camera, but is monitored by its childrenc: The current node does not have a camera and is not monitored by its childrenNext, 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.
a = min(la, lb, lc) + min(ra, rb, rc) + 1.b = min(la + rb, lb + ra, la + ra).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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy Depth-First Search (DFS) | Time Complexity: O(n), where n is the number of nodes in the tree, due to the DFS traversal of every node. |
| Dynamic Programming with Memoization | Time Complexity: O(n), where n is the number of nodes. |
| Dynamic Programming (Tree DP) | — |
| 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 |
Cameras In Binary Tree | Leetcode 968 Binary Tree Cameras • Pepcoding • 30,495 views views
Watch 9 more video solutions →Practice Binary Tree Cameras with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor