Binary Tree Cameras

Given the root of a binary tree, place the minimum number of cameras so that every node is monitored. A camera at a node monitors its parent, itself, and its immediate children. This is a standard tree DP problem because each node can be in one of several coverage states.

Input Format

tree = level-order binary tree with null markers

Output Format

minimum number of cameras

Constraints

  • 1 <= number of nodes <= 10^5
  • Node values are placeholders only and may be ignored.
  • The tree is given in level-order form with null markers.

Examples

Example 1:

Input:

tree = [0,0,null,0,0]

Output:

1

Explanation:

A single camera at the left child can cover the root and both of its children.

Example 2:

Input:

tree = [0,0,0,null,null,0,0]

Output:

2

Explanation:

Two cameras are needed to cover both sides of the tree efficiently.

Loading...
Binary Tree Cameras - Advanced Trees DSA Problem