968. Binary Tree Cameras LeetCode Solution

Last updated: February 21, 2025

In this guide, you will get 968. Binary Tree Cameras LeetCode Solution with the best time and space complexity. The solution to Binary Tree Cameras problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Binary Tree Cameras solution in C++
Binary Tree Cameras solution in Java
Binary Tree Cameras solution in Python
Additional Resources

968. Binary Tree Cameras LeetCode Solution image

Problem Statement of Binary Tree Cameras

You are given the root of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children.
Return the minimum number of cameras needed to monitor all nodes of the tree.

Example 1:

Input: root = [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.

Example 2:

Input: root = [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

Constraints:

The number of nodes in the tree is in the range [1, 1000].
Node.val == 0

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(h)

968. Binary Tree Cameras LeetCode Solution in C++

class Solution {
 public:
  int minCameraCover(TreeNode* root) {
    vector<int> ans = dfs(root);
    return min(ans[1], ans[2]);
  }

 private:
  // 0 := all the nodes below the root are covered except the root
  // 1 := all the nodes below and including the root are covered with no camera
  // 2 := all nodes below and including the root are covered with a camera
  vector<int> dfs(TreeNode* root) {
    if (root == nullptr)
      return {0, 0, 1000};

    vector<int> l = dfs(root->left);
    vector<int> r = dfs(root->right);

    const int s0 = l[1] + r[1];
    const int s1 = min(l[2] + min(r[1], r[2]),  //
                       r[2] + min(l[1], l[2]));
    const int s2 = min({l[0], l[1], l[2]}) +  //
                   min({r[0], r[1], r[2]}) + 1;
    return {s0, s1, s2};
  }
};
/* code provided by PROGIEZ */

968. Binary Tree Cameras LeetCode Solution in Java

class Solution {
  public int minCameraCover(TreeNode root) {
    int[] ans = dfs(root);
    return Math.min(ans[1], ans[2]);
  }

  // 0 := all the nodes below the root are covered except the root
  // 1 := all the nodes below and including the root are covered with no camera
  // 2 := all nodes below and including the root are covered with a camera
  private int[] dfs(TreeNode root) {
    if (root == null)
      return new int[] {0, 0, 1000};

    int[] l = dfs(root.left);
    int[] r = dfs(root.right);

    final int s0 = l[1] + r[1];
    final int s1 = Math.min(l[2] + Math.min(r[1], r[2]), //
                            r[2] + Math.min(l[1], l[2]));
    final int s2 = Math.min(l[0], Math.min(l[1], l[2])) + //
                   Math.min(r[0], Math.min(r[1], r[2])) + 1;

    return new int[] {s0, s1, s2};
  }
}
// code provided by PROGIEZ

968. Binary Tree Cameras LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents