Fewest Watchers on a Tree
Problem
A watcher placed on a node of a binary tree keeps an eye on that node, its parent and its children. Return the fewest watchers needed so that every node in the tree is watched. An empty tree needs none.
Examples
Input: tree = 1, left 2, whose children are 3 and 4
Output: 1
Why: a watcher on 2 covers 1, 3 and 4 as well as itselfInput: tree = a chain of five nodes, each the left child of the one before
Output: 2
Why: watchers on the second and fourth nodes cover all fiveInput: tree = a single node
Output: 1
Why: edge case, the root has to watch itselfHints
0 / 3
Leaves are the most constrained nodes: a leaf can only be watched by itself or by its parent, and the parent covers more of the tree.
Decide from the bottom up. A subtree can end in three situations: its root holds a watcher, its root is watched by a child, or its root is still unwatched and relies on its parent. Everything below the root is covered in all three.
For each node, compute the cheapest cost of each situation from its children's three costs. Holding a watcher allows any child state; being watched needs at least one child holding a watcher and the rest holding or watched; staying unwatched needs every child watched by its own children. The answer is the cheaper of the root's first two costs.
Solution
Each node returns three costs for its subtree, always with everything below the node covered: the node holds a watcher, the node is watched by a child, or the node waits for its parent. A missing child counts as already watched at no cost and can never hold a watcher. A watcher on the node lets each child take its cheapest state, including waiting; the watched state takes each child's better of holding or watched and pays the smallest extra to make one child hold a watcher. The root has no parent, so its waiting state is not allowed. Time is O(n) and space is O(h) for the recursion, for a tree of height h.
INF = float("inf")
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def fewest_watchers(root):
def costs(node):
# (holds a watcher, watched by a child, waits for its parent)
if not node:
return INF, 0, INF # nothing to watch, cannot hold one
kids = (costs(node.left), costs(node.right))
hold = 1 + sum(min(k) for k in kids) # this watcher also covers the children
base = sum(min(h, w) for h, w, _ in kids)
watched = base + min(h - min(h, w) for h, w, _ in kids) # one child must hold
waits = sum(w for _, w, _ in kids)
return hold, watched, waits
return min(costs(root)[:2]) if root else 0
print(fewest_watchers(T(1, T(2, T(3), T(4))))) # -> 1
print(fewest_watchers(T(1, T(2, T(3, T(4, T(5))))))) # -> 2
print(fewest_watchers(T(9))) # -> 1Stuck on the idea rather than the code? DP on Trees covers it.