Skip to main content
Talentd

Binary Tree Cameras - Solution & Explanation

HardDynamic ProgrammingTreeDepth-First SearchBinary Tree19 min readAsked at: Amazon, Microsoft, Goldman Sachs +11
Practice this problem

Problem Statement

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:

  • The number of nodes in the tree is in the range [1, 1000].
  • Node.val == 0

Approach Overview

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.

Approach 1: Greedy Depth-First Search (DFS)

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Dynamic Programming with Memoization

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.

Code

Python

Python

Complexity

Time Complexity: O(n), where n is the number of nodes.
Space Complexity: O(n), due to memoization storage.

Try this approach in the editor →

Approach 3: Dynamic Programming (Tree DP)

For each node, we define three states:

  • a: The current node has a camera
  • b: The current node does not have a camera, but is monitored by its children
  • c: The current node does not have a camera and is not monitored by its children

Next, 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.

  • If the current node has a camera, then its left and right children must be in a monitored state, i.e., a = min(la, lb, lc) + min(ra, rb, rc) + 1.
  • If the current node does not have a camera but is monitored by its children, then one or both of the children must have a camera, i.e., b = min(la + rb, lb + ra, la + ra).
  • If the current node does not have a camera and is not monitored by its children, then the children must be monitored by their children, i.e., 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(h), where h is the height of the tree, due to the recursion stack space.

Dynamic Programming with Memoization

Time Complexity: O(n), where n is the number of nodes.
Space Complexity: O(n), due to memoization storage.

Dynamic Programming (Tree DP)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with MemoizationO(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

Video Solution

Cameras In Binary Tree | Leetcode 968 Binary Tree Cameras • Pepcoding • 31,079 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Binary Tree Cameras easy or hard?
Binary Tree Cameras is categorized as a hard problem because it requires recognizing the correct greedy state transitions during DFS. Once the three-state model is understood, the implementation becomes relatively compact.
How to solve Binary Tree Cameras in O(n)?
Perform a postorder DFS and assign states to each node: 0 for not covered, 1 for a camera placed, and 2 for covered. If any child is uncovered, place a camera at the current node. If any child has a camera, the node becomes covered. Otherwise it remains uncovered so the parent can handle it.
Binary Tree Cameras Python or Java solution
Both Python and Java implementations follow the same DFS strategy. A recursive function returns the coverage state of each node and increments a camera counter when a camera must be placed. The algorithm processes every node once, giving O(n) time complexity.
What is the best approach for Binary Tree Cameras?
The greedy depth-first search approach is the most efficient and commonly expected solution. Each node returns one of three states: uncovered, covered, or has a camera. Cameras are placed only when a child is uncovered, which guarantees minimal placement. This solution runs in O(n) time and uses O(h) recursion space.
What data structure is used in Binary Tree Cameras?
The problem operates on a binary tree and is typically solved using depth-first search recursion. Some solutions also model the problem using dynamic programming states stored per node in the tree.
What is the time complexity of Binary Tree Cameras?
The optimal solution runs in O(n) time because every node in the binary tree is visited exactly once during the DFS traversal. The space complexity is O(h), where h is the height of the tree, due to recursion stack usage.
Is Binary Tree Cameras asked at Google Amazon or Meta?
Binary Tree Cameras is a classic tree greedy problem that appears in interview preparation lists for companies like Google, Amazon, and Meta. It tests understanding of DFS traversal, tree state management, and greedy placement strategies.

Ready to solve this problem?

Practice Binary Tree Cameras with our built-in code editor and test cases.

Practice on FleetCode
Previous

Choose Edges to Maximize Score in a Tree

Next

Distribute Coins in Binary Tree