Solution: Binary Tree Cameras

Let’s solve the Binary Tree Cameras using the Dynamic Programming pattern.

We'll cover the following

Statement

You are given the root of a binary tree. Cameras can be installed on any node, and each camera can monitor itself, its parent, and its immediate children.

Your task is to determine the minimum number of cameras required to monitor every node in the tree.

Constraints:

  • The number of nodes in the tree is in the range [1,1000][1, 1000].

  • Node.data ==0== 0

Solution

Each node in the tree can be in one of three possible states, based on how it's monitored:

  • State 0 (Not covered): All the nodes below this node are monitored, but this node is not.

  • State 1 (Covered, no camera): All the nodes below, including this node, are monitored, but there is no camera at this node.

  • State 2 (Has camera): A camera is installed at this node, monitoring itself, its parent, and its immediate children.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.