Tree: Depth-First Search - Binary Tree Cameras
Given the following tree and the optimal greedy postorder camera placement code, what is the minimum number of cameras placed?
Tree:
0
/ \
0 0
/ \
0 0
Given the following tree and the optimal greedy postorder camera placement code, what is the minimum number of cameras placed? Tree: 0 / \ 0 0 / \ 0 0
easy🧾 Code Trace Q3 of Q15
Step-by-Step Solution
Solution:
Step 1: Trace dfs on leaf nodes
Leaves return NOT_COVERED, causing parents to place cameras.Step 2: Place camera at node with two uncovered children
The right child of root has two leaves uncovered, so place camera there.Step 3: Root is covered by child's camera, no extra camera needed
Root returns COVERED_NO_CAM, so no camera added at root.Final Answer:
Option B -> Option BQuick Check:
Only one camera at right child covers entire tree [OK]
Quick Trick: Camera placed at node with uncovered children [OK]
Common Mistakes:
MISTAKES- Placing cameras on all leaves or root unnecessarily
Trap Explanation:
PITFALL- Candidates often overcount cameras by placing on leaves instead of parents.
Interviewer Note:
CONTEXT- Tests ability to mentally execute DFS with coverage states
Master "Binary Tree Cameras" in Tree: Depth-First Search
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Tree: Depth-First Search Quizzes