Pattern visualizer

Binary Tree Cameras

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

Greedy tri-state DFS: cover from the leaves up

time O(n)space O(h) recursion stackstep 1 / 10

line 1

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

Where to practice Binary Trees

Practice Binary Trees problems All Binary Trees problems Back to roadmap