Find the minimum number of switches to be turned on for illuminating the binary tree

algorithm

Solution

You can solve it recursively by considering what is the minimum number of switches that need to be turned on for each sub-tree, assuming the root node is on and also assuming it is off.

If the root node is on then the child nodes can be either on or off, so `minSwitchesAssumingRootOn` calls `minSwitches` recursively. If the root node is off then the child nodes must be on for the edges connected to the root node to be on, so `minSwitchesAssumingRootOff` calls `minSwitchesAssumingRootOn` recursively.

The sub-totals can be stored using memo-ization to speed it up. `tree.minAssumingOff` and `tree.minAssumingOn` should be initialized to -1.

Pseudo-code:

int minSwitches(tree)
{
    if(tree == null)
        return 0;
    return min(minSwitchesAssumingRootOff(tree),
       minSwitchesAssumingRootOn(tree));
}

int minSwitchesAssumingRootOn(tree)
{
    if(tree == null)
        return 0;
    if(tree.minAssumingOn == -1)
        tree.minAssumingOn = 1 + minSwitches(tree.left) + minSwitches(tree.right);
    return tree.minAssumingOn;
}

int minSwitchesAssumingRootOff(tree)
{
    if(tree == null)
        return 0;
    if(tree.minAssumingOff == -1)
        tree.minAssumingOff = minSwitchesAssumingRootOn(tree.left) + 
            minSwitchesAssumingRootOn(tree.right);
    return tree.minAssumingOff;
}

Problem

Original source