Minimum Cameras to Monitor a Binary Tree
Updated
Problem statement
Given a nonempty binary tree root, return the minimum number of cameras needed to monitor every node. A camera placed at a node monitors that node, its parent if one exists, and its immediate left and right children if they exist.
Place at most one camera at any node. Node values do not affect coverage; equal values may belong to different nodes. The input uses the usual level-order tree array with null for missing children.
Function
minimumTreeCameras(root: TreeNode) → intExamples
Example 1
root = [0,0,null,0,0]return = 1One camera at the root's left child covers that child, the root, and both grandchildren.
Example 2
root = [0,0,0,0,0,0,0]return = 2Cameras at both children of the root cover all seven nodes. A single camera cannot cover leaves in both subtrees.
Constraints
- The tree contains 1 to 1000 non-null nodes.
- The canonical level-order array has 1 to 1999 slots, including nulls.
- Every non-null node value is an integer from 0 through 1000.
- The root is non-null and every serialized non-null node is attached to the tree.
More OYO Rooms Phone Screen questions
Similar questions at other companies
- Binary Tree CamerasAmazon · OA · PHONE SCREEN
- Minimum Rounds to Inform an N-ary TreeRippling · PHONE SCREENRippling interview questions
- Minimum Satellite Data Transfer IterationsHSBC · OAHSBC interview questions
- Split Array to Minimize the Largest SumNation with NaMo · PHONE SCREEN
- File Encryption Tree OptimizationDatabricks · PHONE SCREEN · ONSITE INTERVIEWDatabricks interview questions
- Lowest Common Manager for Employee GroupsGoogle · PHONE SCREENGoogle interview questions
- Stock Profit With One, Unlimited, or Two TradesAdobe · PHONE SCREENAdobe interview questions
- Maximum Path Sum Between Marked NodesDoorDash · PHONE SCREENDoorDash interview questions
- House Robber IIIOkta · PHONE SCREENOkta interview questions
- House Robber IIIGoldman Sachs · PHONE SCREENGoldman Sachs interview questions