Cameras on a Tree

#441 · Trees · Expert · 220 XP · about 40 min

You want to watch every node of a binary tree with security cameras. A camera placed on a node watches that node, its parent and its children. Write min_cameras(root) that returns the smallest number of cameras that together watch every node. An empty tree needs no cameras.

Each node is a Node with a value val and two children, left and right, which are None when missing. The provided build makes a tree from a list of values in level order, where None marks a missing child.

Examples

min_cameras(build([0, 0, None, 0, 0]))  # returns 1
min_cameras(build([0, 0, None, 0, None, 0, None, None, 0]))  # returns 2
min_cameras(build([0]))  # returns 1

The drawing shows the first tree: one camera on the middle node watches all four nodes. The second tree is a chain of five nodes, which needs two cameras, for example on the second and the fourth node.

Constraints

0 to 50,000 nodes, at most 700 levels deep. The values do not matter.

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.

# Provided: do not change

from collections import deque

class Node:

def __init__(self, val, left=None, right=None):

self.val = val

self.left = left

self.right = right

def build(values):

"""Build a tree from a level-order list; None marks a missing child."""

if not values or values[0] is None:

return None

root = Node(values[0])

queue = deque([root])

i = 1

while queue and i < len(values):

node = queue.popleft()

if values[i] is not None:

node.left = Node(values[i])

queue.append(node.left)

i += 1

if i < len(values) and values[i] is not None:

node.right = Node(values[i])

queue.append(node.right)

i += 1

return root

def min_cameras(root):

# Your code here

pass

print(min_cameras(build([0, 0, None, 0, 0])))

Ready?

Accept the challenge to start writing. A small timer counts the time this page is in view.

Output appears here.