Fewest Guards on a Tree

Hard

A company's servers form a network shaped like a binary tree with root root. A watchdog program can be installed on any server. A watchdog on a server monitors that server, its parent, and its direct children. Return the smallest number of watchdogs needed so that every server in the tree is monitored. Node values carry no meaning: they are all 0.

Example 1

root=tree_node([0, 0, 0, 0, None, None, 0]) → 2

One guard on each child of the root: the left one watches the root and its own child, the right one watches its own child. A single guard cannot cover all five nodes.

Example 2

root=tree_node([0, 0, None, 0, None, 0]) → 2

A chain of four nodes: a guard on the second node watches the first three, and the fourth needs one more.

Example 3

root=tree_node([0]) → 1

Constraints

1 ≤ number of nodes ≤ 1000
Node.val = 0

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Dynamic Programming Binary Tree

Similar problems

Heaviest Path in a Tree Hard Heaviest Search Subtree Hard Biggest Search Subtree Medium A Party Without Direct Bosses Medium Zigzag Tree Descent Medium

Input

root=tree_node([0, 0, 0, 0, None, None, 0])

Expected

Run checks the first 3 tests in your browser. Submit checks all 110 tests on the server, hidden ones included.