Minimum number of phones

Question

Your are given a binary tree which contains family members. You are asked to find the total number of mobile phones that are required for the family in order to communicate under the condition that each person can share their mobile with their parent and children whereas a shared mobile can't be shared further.

int minPhones(struct TreeNode* root){

    //base case

    if(root == NULL)
    {
        return 0;
    }

    int phones = 0;
    int shared = 2;
    int phonesNeeded(struct TreeNode* node)
    {
        if(node == NULL)
        {return 0;}
        if((node->left == NULL ||  (node->left->left == NULL && node->left->right == NULL))&& (node->right == NULL ||  (node->right->left == NULL && node->right->right == NULL)))
        {
            shared = 1;
            return 1;
        }
        if(shared == 1)
        {
            shared = 0;
            return 0;
        }
        else if(shared == 0)
        {
            return 1;
        }
        return phonesNeeded(node->left) + phonesNeeded(node->right);
    }
    phones = phonesNeeded(root) + 1;
    return phones;
}

This is the code I have written and would like to ask how to modify this code to the required output.

Answer 1

Call a node covered if it has a phone or a phone is shared with it because a parent or child of it has a phone.

To cover a leaf node, either it or its parent must have a phone.

Except in a tree with only a root, there is never any advantage to assigning a phone to a leaf node because assigning a phone to its parent provides a superset of coverage:

• Assigning the phone to a leaf node covers it and its parent (unless it has none, and hence the tree is only one node) and no other nodes.
• Assigning the phone to the leaf node’s parent covers the leaf node, its parent, its grandparent (if it exists), and its sibling (if it exists).

Therefore, we should assign phones to all parents of leaves. Once that is done, we can remove from the tree all covered nodes without any uncovered children and then apply the above again: Assigning a phone to a leaf node in the remaining tree would not provide new coverage for its previous child or children, since those previous children are already covered, so the analysis of which nodes a phone provides coverage to is the same as above.

So an optimal algorithm is:

• While the tree is not empty:
  • If there is only one node, assign a phone to it and stop.
  • Assign a phone to the parent of each leaf node (only one even if it has two leaf node children).
  • Remove from the tree all covered nodes without any uncovered children.

Note that the algorithm maybe implemented, if desired, by marking nodes covered and determining leaf nodes with respect to that coverage, rather than by actually deconstructing the tree.

I think an equivalent statement of the algorithm is:

• While there is an uncovered node:
  • If there is only one node, assign a phone to it and stop.
  • Assign a phone to the parent of each node with no uncovered children.

Here is candidate prototype code I have not tested:

typedef struct Node { struct Node *left, *right; } Node;

void AssignPhone(Node *);

typedef enum { HavePhone, CoveredByChild, Uncovered, DoesNotExist } Coverage;


static Coverage Process(Node *p)
{
    Coverage LeftCoverage  = p->left  ? Process(p->left ) : DoesNotExist;
    Coverage RightCoverage = p->right ? Process(p->right) : DoesNotExist;
    if (LeftCoverage == Uncovered || RightCoverage == Uncovered)
    {
        AssignPhone(p);
        return HavePhone;
    }
    if (LeftCoverage == HavePhone || RightCoverage == HavePhone)
        return CoveredByChild;
    return Uncovered;
}


void ProcessRoot(Node *p)
{
    if (Process(p) == Uncovered)
        AssignPhone(p);
}