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 == 0The key idea in Binary Tree Cameras is to place the minimum number of cameras so that every node in the binary tree is monitored. A camera at a node can monitor its parent, itself, and its immediate children. The most effective strategy uses a post-order Depth-First Search (DFS) combined with a small state-based dynamic programming idea.
During traversal, each node returns a state describing whether it has a camera, is covered, or is not covered. By processing children first, the algorithm decides if a camera must be placed at the current node (for example, when a child is not covered). This greedy decision works because information flows upward from the leaves to the root.
This DFS approach ensures cameras are placed only when necessary, leading to an optimal solution. Since each node is processed once, the algorithm runs in O(n) time with O(h) recursion space, where n is the number of nodes and h is the tree height.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS with Greedy State Tracking | O(n) | O(h) |
| Tree DP with Post-order Traversal | O(n) | O(h) |
NeetCode
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.
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.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode
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.
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.
Time Complexity: O(n), where n is the number of nodes.
Space Complexity: O(n), due to memoization storage.
1from functools import lru_cache
2
3class TreeNode:
4 def
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Binary Tree Cameras is a classic hard tree problem that reflects concepts commonly tested in FAANG interviews. It evaluates understanding of DFS, greedy strategies, and tree-based dynamic programming.
The optimal approach uses a post-order DFS with state tracking. Each node reports whether it has a camera, is covered, or is not covered. This allows the algorithm to greedily place cameras only when necessary, ensuring the minimum number of cameras.
Post-order traversal processes child nodes before their parent, which allows the algorithm to determine whether the parent needs a camera based on the coverage status of its children. This bottom-up decision-making ensures optimal placement.
A binary tree structure combined with recursion or a stack for DFS traversal works best. The solution relies on post-order traversal to evaluate children before deciding whether to place a camera at the current node.
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.