Fewest Watchtowers
HardTrees
Problem
A park's trail junctions form a binary tree. A watchtower built on a junction monitors that junction, its parent and its children.
Given the root, return the minimum number of watchtowers needed so that every junction is monitored. Node values are irrelevant (all 0).
Example 1
- Input:
- root = [0, 0, null, 0, 0]
- Output:
- 1
One tower on the root's left child covers all four junctions.
Example 2
- Input:
- root = [0, 0, null, 0, null, 0, null, null, 0]
- Output:
- 2
A chain of five junctions needs two towers, e.g. on the second and fourth.
Constraints
- 1 ≤ number of nodes ≤ 1000
- Tree height ≤ 500
- node.val == 0
Hint
Show the first hint
Look at a deepest leaf. A tower on the leaf covers fewer junctions than a tower on its parent. What does that suggest?
Walkthrough
How to approach it
01Clarify before coding
- Does a tower cover grandchildren? No: itself, parent and children only.
- Is a single node a valid tree? Yes, it needs one tower.
- Do values matter? No.
02Brute force
Try all subsets of junctions and keep the smallest that covers everything.
Cost: O(2^n · n): impossible beyond about 25 nodes.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.