Binary Tree Cameras

Greedy tri-state DFS: cover from the leaves up

time O(n)space O(h) recursion stack

A camera on a leaf only ever covers that leaf and its parent, wasting the chance to also cover a grandparent — so cameras should sit as high up as necessary, never lower. Working bottom-up, each node tells its parent one of three things: I still need a camera, I have one, or I'm covered without one. A parent places a camera only when forced to — when a child reports it still needs one — because that single camera then also covers the parent's own parent for free.

Details

Animated on: root = [0,0,null,0,0] — install the minimum number of cameras on tree nodes so a camera monitors itself, its parent, and its children. Expected: 1.

Problem:Binary Tree CamerasHard

Greedy tri-state DFS: cover from the leaves up

step 1 / 10

Call solve(r). Work bottom-up: each node reports one of three states to its parent — needs a camera, has a camera, or is covered by a neighbour's camera — and a camera goes on a node only when a child of it is still uncovered.

Pseudocode

1FUNCTION solve(node):
2  IF node = null:  RETURN COVERED
3  left <- solve(node.left)
4  right <- solve(node.right)
5  IF left = NEEDS_CAM OR right = NEEDS_CAM:
6    cameras <- cameras + 1
7    RETURN HAS_CAMERA
8  IF left = HAS_CAMERA OR right = HAS_CAMERA:
9    RETURN COVERED
10  RETURN NEEDS_CAM
11END FUNCTION
12IF solve(root) = NEEDS_CAM:  cameras <- cameras + 1

← / → step · space play · Home restart

Every step in words

Show all 10 steps

Call solve(r). Work bottom-up: each node reports one of three states to its parent — needs a camera, has a camera, or is covered by a neighbour's camera — and a camera goes on a node only when a child of it is still uncovered.
Enter solve(r). Recurse into its left child, a, first.
Enter solve(a). Recurse into its left child, b, first.
Enter solve(b). It has no left child, which counts as already covered.
Both of b's children are covered but neither carries a camera (left=covered, right=covered), so b itself is not yet monitored by anyone. It reports "needs cam" and leaves the decision to its parent.
Enter solve(c). It has no left child, which counts as already covered.
Both of c's children are covered but neither carries a camera (left=covered, right=covered), so c itself is not yet monitored by anyone. It reports "needs cam" and leaves the decision to its parent.
a has a child reporting "needs cam" (left=needs cam, right=needs cam), so a camera goes here instead of on the child — one camera covers the child, this node, AND its parent. Cameras placed so far: 1.
r has a child with a camera (left=camera, right=covered), so r is already covered without needing one of its own.
The root's final state is "covered", not "needs cam", so no extra camera is needed there. Done: 1 camera in total.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Binary Tree Cameras in the editor All Binary Trees problems Back to roadmap