Tree: Depth-First Search - Binary Tree Cameras
Consider the optimal camera placement code. What is the output when the input tree is a single node (root only)?
Consider the optimal camera placement code. What is the output when the input tree is a single node (root only)?
medium🧾 Code Trace Q4 of Q15
Step-by-Step Solution
Solution:
Step 1: dfs on null children returns COVERED_NO_CAM
Left and right children are null, so dfs returns COVERED_NO_CAM (1).Step 2: Both children covered but no camera, so root returns NOT_COVERED
Since left and right are COVERED_NO_CAM, root returns NOT_COVERED (0).Step 3: After dfs, root is NOT_COVERED, so add one camera
Increment cameras to 1.Final Answer:
Option A -> Option AQuick Check:
Single node requires one camera [OK]
Quick Trick: Root uncovered after dfs triggers camera addition [OK]
Common Mistakes:
MISTAKES- Assuming no camera needed for single node
Trap Explanation:
PITFALL- Candidates forget to add camera if root remains uncovered after traversal.
Interviewer Note:
CONTEXT- Tests handling of minimal edge cases and root coverage logic
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