Problem statement

https://leetcode.com/problems/binary-tree-cameras/

Solution

In by opition, this is really nice problem on the edge of two topics: binary trees and dynamic programming. We need to traverse our tree in some way and keep some information in nodes. We can say that we use here postorder traversal: to get the answer for some node, we first collect answers for its children and then construct answer for node. We will keep 3 pieces of information in each node:

  1. q1: minimum number of cameras for subtree if we put camera on this node
  2. q2: minimum number of cameras for subtree if we do not put camera on this node
  3. q3: minimum number of cameras for subtree, not including node itself, that is node is not covered

First of all, the border cases: if we reached None node, q1 will be infinite, because we need to put camera on not-existing node, q2 and q3 are equal to 0.

Then we calculate values for the left subtree: q1_l, q2_l, q3_l and for the right subtree q1_r, q2_r, q3_r.

  1. How we can evaluate q1 now? By definition it is number of cameras for subtree if we put camera on this node. We also need to cover left and right subtrees fully. For left subtree we can choose q1_l or q2_l or q3_l options, but in fact q2_l is always bigger or equal then q3_l, so we can choose only among two options. The same logic is for the right subtree. Note, that it was important here to have q3-s values, because we do not really need to cover left and right children, then already covered by node (but also we can not say we need to use q3 always, there are greedy algorithms that works, but not like this)
  2. How we can evaluate q2 now? By definition we are not allowed to put camera on Node, so we need to fully cover left and right subtree. We can not use any q3_l or q3_r, because we will have gap in this case. We can use any from q1_l, q2_l for the left subtree and any from q1_r, q2_r for the right subtree, so we will choose minimum from 4 combinations However we need to remove case q2_l + q2_r, because in this case node will not be covered.
  3. Howe we can evaluate q3 now? As I mentionend, q3 ia always not smaller than q2, so one of the options is to just take q2. Or we can take q2_l + q2_r. Why? By definition we do not need to cover node. So for the left and right nodes we just need to cover all subtrees, but also we do not need to cover node itself, so q2_l and q2_r are enough. Note, that we can not use q1_l or q1_r here, because we will break the condition of not cover node

Complexity

Time complexity is O(n) for traverse all the tree, space complexity is O(h), where h is the height of the tree.

Code

class Solution:
    def minCameraCover(self, root):
        def dfs(node):
            if not node: return (float("inf"), 0, 0)
            q1_l, q2_l, q3_l = dfs(node.left)
            q1_r, q2_r, q3_r = dfs(node.right)
            q1 = min(q1_l, q3_l) + min(q1_r, q3_r) + 1
            q2 = min(q1_l + q1_r, q1_l + q2_r, q2_l + q1_r)
            q3 = min(q2, q2_l + q2_r)
            return (q1, q2, q3)
            
        return min(dfs(root)[:2])