Tree: Depth-First Search - Binary Tree Cameras
Given the following code for the optimal camera placement, what is the final number of cameras placed for the tree with root node 0, left child 1, and right child 2 (both children are leaves)?
Given the following code for the optimal camera placement, what is the final number of cameras placed for the tree with root node 0, left child 1, and right child 2 (both children are leaves)?
easy🧾 Code Trace Q12 of Q15
Step-by-Step Solution
Step 1: Trace dfs on leaf nodes 1 and 2
Leaves return NOT_COVERED (0) because their children are null and return COVERED_NO_CAM (1). So dfs(1) and dfs(2) return NOT_COVERED.Step 2: At root node 0, left or right child is NOT_COVERED, so place a camera here
Increment cameras to 1 and return HAS_CAM (2). The root is covered, so no extra camera needed.Final Answer:
Option D -> Option DQuick Check:
One camera at root covers all nodes [OK]
Quick Trick: Leaves uncovered -> camera at parent -> minimal cameras [OK]
Common Mistakes:
MISTAKES- Counting cameras on leaves instead of parent
- Forgetting to add camera at root if uncovered
- Misinterpreting coverage states
Trap Explanation:
PITFALL- Some think cameras are needed on leaves, but placing at root suffices.
Interviewer Note:
CONTEXT- Checks candidate's ability to mentally execute DFS with 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