Given a binary tree, place cameras to monitor all nodes

Use post-order DFS with three states per node:Uncovered — subtree needs a camera above or at this node.Covered — subtree monitored, no camera needed here.Has camera — camera placed on this node.Transition: if any child is uncovered, place camera on current node. If any child has camera, mark current covered. Else mark uncovered.Time O(n), space O(h) for recursion stack. Mention iterative stack if interviewer prefers.

Learn Netverks Curriculum map

AM Company prep Amazon

Mid-level (3–5 years) Coding / DSA Hard

Tree DP pattern frequently reported in Amazon SDE-2 coding rounds.

Role: SDE-2
Location: Hyderabad
Study track: Java

Interview scenario

Follow-up: optimize for minimum cameras. Expect discussion of post-order traversal and state machine on nodes.

Spoiler-free prep mode

Use post-order DFS with three states per node:

Uncovered — subtree needs a camera above or at this node.
Covered — subtree monitored, no camera needed here.
Has camera — camera placed on this node.

Transition: if any child is uncovered, place camera on current node. If any child has camera, mark current covered. Else mark uncovered.

Time O(n), space O(h) for recursion stack. Mention iterative stack if interviewer prefers.

Discussion

Comments (0)

Share how this question came up in your loop, or add tips for others preparing.

Interview scenario

Try answering aloud first

Comments (0)