HardDynamic ProgrammingTreeDepth-First SearchBinary TreeUpdated Sep 2026

968. Binary Tree Cameras

Asked at DE Shaw

Difficulty

Hard

Time

O(n)

Space

O(h)

Pattern

Dynamic Programming

Companies

1

Problem

You are given the root of a binary tree. You may place cameras on any nodes. A camera placed on a node watches three things: the node itself, its parent, and its direct children.

Return the minimum number of cameras needed so that every node in the tree is watched by at least one camera.

A node does not need its own camera if a camera on its parent, on itself, or on one of its children can see it. The tree can have as few as one node.

One camera watches three spots

0watched0camera here0watched0watchedA single camera on the root's left child sees all fournodes
A camera on a node covers that node, its parent and its children — so a camera on the middle node covers the whole chain.

Constraints

  • ●The number of nodes is in the range [1, 1000].
  • ●Node.val == 0 for every node.

Examples

Example 1
Inputroot = [0,0,null,0,0]
Output1
WhyThe tree is a chain: root → left child → its two children. Put one camera on the middle node (the root's left child). That camera sees itself, the root above it, and both leaves below it, so all four nodes are watched with a single camera.
Example 2
Inputroot = [0,0,null,0,null,0,null,null,0]
Output2
WhyThis is a longer chain. One camera cannot reach both ends, so two cameras are needed. For example, place one camera on the node two steps down and one on the deepest node; together they cover every node.

Asked At

1 companies
CompanyDifficulty
DE ShawHardView all DE Shaw questions →

How to Think About It

1

Placing a camera on a leaf covers only the leaf and its parent. Placing it on the leaf's parent covers the leaf, the parent, and the grandparent — strictly better.

2

Key insight: process bottom-up (post-order) and have each node report one of three states to its parent: 0 = not covered, 1 = has a camera, 2 = covered without a camera.

3

Rules at a node: if any child is 0 (uncovered), this node must hold a camera -> return 1. Else if any child is 1, this node is covered -> return 2. Otherwise both children are covered but neither can see this node -> return 0 and let the parent handle it.

4

Null children count as covered (2) so leaves correctly report 0.

5

After the traversal, if the root itself reports 0, add one more camera at the root.

Optimal Approach

Step 1: cameras = 0.
Step 2: dfs(node):
If node is null, return 2.
l = dfs(node.left), r = dfs(node.right).
If l == 0 or r == 0: cameras += 1; return 1.
If l == 1 or r == 1: return 2.
Return 0.
Step 3: If dfs(root) == 0, cameras += 1.
Step 4: Return cameras.

Time: O(n). Space: O(h).

Bottom-up states: 0, 1, 2

0leaf → 00child 0 → camera, 10leaf → 00Leaves report 0 (uncovered). A parent with anuncovered child must take a camera and report 1.00has camera → 100child 1 → covered, 2The root sees a child with a camera, so it is coveredand reports 2. No extra camera needed.child 0 → put camera, return 1child 1 → covered, return 2both 2 → return 0 (parent must help)
Each node tells its parent one of three things, and the parent decides whether it must hold a camera.
ComplexityTime O(n)Space O(h)Each node is visited once in the post-order walk; h is the tree height, which is the depth of the recursion stack.

What Trips People Up in Real Interviews

1

Greedily putting cameras on leaves or on every other level. Both overcount; the parent-of-leaf rule is what makes the greedy optimal.

2

Treating null children as uncovered. That forces cameras onto every leaf.

3

Forgetting the root check at the end. A root whose children are covered but have no camera is left unmonitored.

4

Checking the "has camera" case before the "uncovered child" case. An uncovered child must win — it forces a camera here.

Solution Code

O(n) time
def minCameraCover(root):
    cameras = 0

    def dfs(node):
        nonlocal cameras
        if not node:
            return 2
        l = dfs(node.left)
        r = dfs(node.right)
        if l == 0 or r == 0:
            cameras += 1
            return 1
        if l == 1 or r == 1:
            return 2
        return 0

    if dfs(root) == 0:
        cameras += 1
    return cameras

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Binary Tree Cameras problem?

Binary Tree Cameras asks for the minimum number of cameras to place on nodes so that every node is monitored, where a camera covers its own node, its parent, and its children. The optimal strategy is a greedy post-order pass: never put a camera on a leaf — put it on the leaf's parent instead.

How do you solve Binary Tree Cameras?

The optimal approach runs in O(n) time and O(h) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Binary Tree Cameras?

Binary Tree Cameras is asked at DE Shaw. It is a hard difficulty problem.

What are common mistakes on Binary Tree Cameras?
  • Greedily putting cameras on leaves or on every other level. Both overcount; the parent-of-leaf rule is what makes the greedy optimal.
  • Treating null children as uncovered. That forces cameras onto every leaf.
  • Forgetting the root check at the end. A root whose children are covered but have no camera is left unmonitored.
  • Checking the "has camera" case before the "uncovered child" case. An uncovered child must win — it forces a camera here.