{"id":"8fbb5417-5ff6-4fba-8bde-938a1a717fc9","name":"Cameras In Binary Tree","description":"1. You are given a partially written function to solve.\r\n2. You are required to complete the body of MinCamerasInBT_ function. The function is expected to return integer value representing minimum number of camera(s) required for the coverage of complete tree.\r\n3.A camera is placed on any node will ensure coverage of parent-node as well as it's child-node(s), if any.\r\n4. Input and Output is managed for you.\r\n\r\n","inputFormat":"Input is managed for you.","outputFormat":"Output is managed for you. ","constraints":"0 &lt;= Number of Nodes &lt;= 10^9\r\n-10^9 &lt;= value of Node data &lt;= 10^9","sampleCode":{"cpp":{"code":"#include <iostream>\r\n#include <vector>\r\nusing namespace std;\r\n\r\nclass TreeNode\r\n{\r\npublic:\r\n int val = 0;\r\n TreeNode *left = nullptr;\r\n TreeNode *right = nullptr;\r\n\r\n TreeNode(int val)\r\n {\r\n this->val = val;\r\n }\r\n};\r\n\r\nint MinCamerasInBT(TreeNode *root)\r\n{\r\n return 0;\r\n}\r\n\r\n// input_Section_====================================================================\r\n\r\nTreeNode *createTree(vector<int> &arr, vector<int> &IDX)\r\n{\r\n if (IDX[0] > arr.size() || arr[IDX[0]] == -1)\r\n {\r\n IDX[0]++;\r\n return nullptr;\r\n }\r\n\r\n TreeNode *node = new TreeNode(arr[IDX[0]++]);\r\n node->left = createTree(arr, IDX);\r\n node->right = createTree(arr, IDX);\r\n\r\n return node;\r\n}\r\n\r\nvoid solve()\r\n{\r\n int n;\r\n cin >> n;\r\n vector<int> arr(n, 0);\r\n for (int i = 0; i < n; i++)\r\n {\r\n cin >> arr[i];\r\n }\r\n\r\n vector<int> IDX(1, 0);\r\n TreeNode *root = createTree(arr, IDX);\r\n cout << MinCamerasInBT(root) << endl;\r\n}\r\n\r\nint main()\r\n{\r\n solve();\r\n return 0;\r\n}"},"java":{"code":"import java.util.Scanner;\r\n\r\npublic class Main {\r\n public static Scanner scn = new Scanner(System.in);\r\n\r\n public static class TreeNode {\r\n int val = 0;\r\n TreeNode left = null;\r\n TreeNode right = null;\r\n\r\n TreeNode(int val) {\r\n this.val = val;\r\n }\r\n }\r\n\r\n public static int MinCamerasInBT(TreeNode root) {\r\n return 0;\r\n }\r\n\r\n // input_Section_====================================================================\r\n\r\n public static TreeNode createTree(int[] arr, int[] IDX) {\r\n if (IDX[0] > arr.length || arr[IDX[0]] == -1){\r\n IDX[0]++;\r\n return null;\r\n }\r\n\r\n TreeNode node = new TreeNode(arr[IDX[0]++]);\r\n node.left = createTree(arr, IDX);\r\n node.right = createTree(arr, IDX);\r\n\r\n return node;\r\n }\r\n\r\n public static void solve() {\r\n int n = scn.nextInt();\r\n int[] arr = new int[n];\r\n for (int i = 0; i < n; i++)\r\n arr[i] = scn.nextInt();\r\n\r\n int[] IDX = new int[1];\r\n TreeNode root = createTree(arr, IDX);\r\n System.out.println(MinCamerasInBT(root));\r\n\r\n }\r\n\r\n public static void main(String[] args) {\r\n solve();\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"15\r\n1\r\n1\r\n-1\r\n1\r\n1\r\n-1\r\n1\r\n-1\r\n-1\r\n1\r\n-1\r\n-1\r\n1\r\n-1\r\n-1","sampleOutput":"3\r\n","questionVideo":"https://www.youtube.com/embed/uoFrIIrp5_g","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"2e9df04c-be14-441c-9a18-8b5a8ca6596d","name":"Trees For Intermediate","slug":"trees-for-intermediate-9994","type":0},{"id":"50ccb80c-9c1c-47ab-8745-ac3f4e240230","name":"Cameras In Binary Tree","slug":"cameras-in-binary-tree","type":1}],"next":{"id":"b11b9b60-e6d1-49b2-85c2-25460cb97bf0","name":"Cameras In Binary Tree","type":3,"slug":"cameras-in-binary-tree"},"prev":{"id":"914fc009-d775-47e2-80d1-a6d306bf6273","name":"Preorder Morris Traversal In Binarytree","type":3,"slug":"preorder-morris-traversal-in-binarytree"}}}

Cameras In Binary Tree

1. You are given a partially written function to solve. 2. You are required to complete the body of MinCamerasInBT_ function. The function is expected to return integer value representing minimum number of camera(s) required for the coverage of complete tree. 3.A camera is placed on any node will ensure coverage of parent-node as well as it's child-node(s), if any. 4. Input and Output is managed for you.

{"id":"8fbb5417-5ff6-4fba-8bde-938a1a717fc9","name":"Cameras In Binary Tree","description":"1. You are given a partially written function to solve.\r\n2. You are required to complete the body of MinCamerasInBT_ function. The function is expected to return integer value representing minimum number of camera(s) required for the coverage of complete tree.\r\n3.A camera is placed on any node will ensure coverage of parent-node as well as it's child-node(s), if any.\r\n4. Input and Output is managed for you.\r\n\r\n","inputFormat":"Input is managed for you.","outputFormat":"Output is managed for you. ","constraints":"0 &lt;= Number of Nodes &lt;= 10^9\r\n-10^9 &lt;= value of Node data &lt;= 10^9","sampleCode":{"cpp":{"code":"#include <iostream>\r\n#include <vector>\r\nusing namespace std;\r\n\r\nclass TreeNode\r\n{\r\npublic:\r\n int val = 0;\r\n TreeNode *left = nullptr;\r\n TreeNode *right = nullptr;\r\n\r\n TreeNode(int val)\r\n {\r\n this->val = val;\r\n }\r\n};\r\n\r\nint MinCamerasInBT(TreeNode *root)\r\n{\r\n return 0;\r\n}\r\n\r\n// input_Section_====================================================================\r\n\r\nTreeNode *createTree(vector<int> &arr, vector<int> &IDX)\r\n{\r\n if (IDX[0] > arr.size() || arr[IDX[0]] == -1)\r\n {\r\n IDX[0]++;\r\n return nullptr;\r\n }\r\n\r\n TreeNode *node = new TreeNode(arr[IDX[0]++]);\r\n node->left = createTree(arr, IDX);\r\n node->right = createTree(arr, IDX);\r\n\r\n return node;\r\n}\r\n\r\nvoid solve()\r\n{\r\n int n;\r\n cin >> n;\r\n vector<int> arr(n, 0);\r\n for (int i = 0; i < n; i++)\r\n {\r\n cin >> arr[i];\r\n }\r\n\r\n vector<int> IDX(1, 0);\r\n TreeNode *root = createTree(arr, IDX);\r\n cout << MinCamerasInBT(root) << endl;\r\n}\r\n\r\nint main()\r\n{\r\n solve();\r\n return 0;\r\n}"},"java":{"code":"import java.util.Scanner;\r\n\r\npublic class Main {\r\n public static Scanner scn = new Scanner(System.in);\r\n\r\n public static class TreeNode {\r\n int val = 0;\r\n TreeNode left = null;\r\n TreeNode right = null;\r\n\r\n TreeNode(int val) {\r\n this.val = val;\r\n }\r\n }\r\n\r\n public static int MinCamerasInBT(TreeNode root) {\r\n return 0;\r\n }\r\n\r\n // input_Section_====================================================================\r\n\r\n public static TreeNode createTree(int[] arr, int[] IDX) {\r\n if (IDX[0] > arr.length || arr[IDX[0]] == -1){\r\n IDX[0]++;\r\n return null;\r\n }\r\n\r\n TreeNode node = new TreeNode(arr[IDX[0]++]);\r\n node.left = createTree(arr, IDX);\r\n node.right = createTree(arr, IDX);\r\n\r\n return node;\r\n }\r\n\r\n public static void solve() {\r\n int n = scn.nextInt();\r\n int[] arr = new int[n];\r\n for (int i = 0; i < n; i++)\r\n arr[i] = scn.nextInt();\r\n\r\n int[] IDX = new int[1];\r\n TreeNode root = createTree(arr, IDX);\r\n System.out.println(MinCamerasInBT(root));\r\n\r\n }\r\n\r\n public static void main(String[] args) {\r\n solve();\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"15\r\n1\r\n1\r\n-1\r\n1\r\n1\r\n-1\r\n1\r\n-1\r\n-1\r\n1\r\n-1\r\n-1\r\n1\r\n-1\r\n-1","sampleOutput":"3\r\n","questionVideo":"https://www.youtube.com/embed/uoFrIIrp5_g","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"2e9df04c-be14-441c-9a18-8b5a8ca6596d","name":"Trees For Intermediate","slug":"trees-for-intermediate-9994","type":0},{"id":"50ccb80c-9c1c-47ab-8745-ac3f4e240230","name":"Cameras In Binary Tree","slug":"cameras-in-binary-tree","type":1}],"next":{"id":"b11b9b60-e6d1-49b2-85c2-25460cb97bf0","name":"Cameras In Binary Tree","type":3,"slug":"cameras-in-binary-tree"},"prev":{"id":"914fc009-d775-47e2-80d1-a6d306bf6273","name":"Preorder Morris Traversal In Binarytree","type":3,"slug":"preorder-morris-traversal-in-binarytree"}}}
plane

Editor

Loading...

Cameras In Binary Tree

hard

1. You are given a partially written function to solve. 2. You are required to complete the body of MinCamerasInBT_ function. The function is expected to return integer value representing minimum number of camera(s) required for the coverage of complete tree. 3.A camera is placed on any node will ensure coverage of parent-node as well as it's child-node(s), if any. 4. Input and Output is managed for you.

Constraints

0 <= Number of Nodes <= 10^9 -10^9 <= value of Node data <= 10^9

Format

Input

Input is managed for you.

Output

Output is managed for you.

Example

Sample Input

15 1 1 -1 1 1 -1 1 -1 -1 1 -1 -1 1 -1 -1

Sample Output

3

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode