Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in C#

Solution: Binary Tree Cameras

Discover how to apply dynamic programming to determine the minimum number of cameras required to monitor every node in a binary tree. This lesson guides you through classifying nodes by coverage states and using post-order traversal to compute optimal placements efficiently. You'll understand how to implement a recursive algorithm to solve this problem with O(n) time complexity.

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 ...