This problem requires placing the fewest cameras to cover every node in a binary tree. By using depth-first search with state tracking for each node—covered, has camera, or not covered—we can determine optimal placement recursively. Dynamic programming ensures overlapping subtrees are computed efficiently, avoiding redundant calculations and minimizing the total number of cameras.
Problem Statement
You are given the root of a binary tree. Each camera placed at a node can monitor its parent, itself, and immediate children. Determine the minimum number of cameras required to cover all nodes in the tree.
For example, given root = [0,0,null,0,0], one camera placement can cover all nodes. For root = [0,0,null,0,null,0,null,null,0], at least two cameras are necessary. Return the smallest number of cameras needed.
Examples
Example 1
Input: root = [0,0,null,0,0]
Output: 1
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
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
- The number of nodes in the tree is in the range [1, 1000].
- Node.val == 0
Solution Approach
Use DFS with Node State Tracking
Traverse the tree using depth-first search. Assign each node a state: 0 for not covered, 1 for covered, 2 for has a camera. Evaluate children first to decide whether the current node needs a camera.
Bottom-Up Recursion
Process leaf nodes first and propagate coverage information upwards. Place cameras on nodes whose children are not covered to ensure minimal placement while all nodes are eventually monitored.
Dynamic Programming Optimization
Cache the results for subtrees to avoid recalculating coverage states. This reduces redundant computation and guarantees that each node's camera placement decision contributes to a global minimum.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(N) |
| Space | O(H) |
Time complexity is O(N) because each node is visited once. Space complexity is O(H) due to recursion stack, where H is the height of the tree.
What Interviewers Usually Probe
- Wants an optimal solution using DFS with minimal cameras
- Interested in how you track node states during traversal
- Checks if you handle edge cases like skewed or leaf-heavy trees
Common Pitfalls or Variants
Common pitfalls
- Placing cameras on every node instead of minimal set
- Failing to correctly propagate covered states from children
- Ignoring the coverage of parent nodes leading to overcounting cameras
Follow-up variants
- Find minimum cameras in n-ary trees instead of binary trees
- Compute camera placement when some nodes cannot hold cameras
- Determine camera placement for dynamic trees that can change structure
How GhostInterview Helps
- Provides step-by-step DFS traversal and state tracking hints
- Explains how to implement bottom-up recursion efficiently
- Highlights minimal camera placement with dynamic programming and edge-case coverage
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the core pattern in Binary Tree Cameras problem?
The main pattern is binary-tree traversal combined with state tracking for covered nodes, which guides minimal camera placement.
How do I determine if a node needs a camera?
Check the states of its children: if any child is not covered, the current node requires a camera to cover them.
Can I solve this without recursion?
Yes, but iterative DFS or BFS with explicit stacks is more complex and requires careful state management for each node.
What are common mistakes when placing cameras?
Placing too many cameras, failing to propagate coverage, or not handling leaf nodes correctly are frequent errors.
How does dynamic programming help in this problem?
It avoids recalculating coverage for subtrees, ensuring optimal camera count while keeping the algorithm efficient.
Need direct help with Binary Tree Cameras instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Binary Tree Cameras from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the longest ZigZag path in a binary tree using depth-first search and dynamic programming for precise node state tracking.
Open problem page#1373 Maximum Sum BST in Binary TreeFind the maximum sum of values from any Binary Search Tree (BST) subtree in a binary tree.
Open problem page#337 House Robber IIIMaximize the loot by robbing non-adjacent houses in a binary tree structure using dynamic programming and DFS.
Open problem page