CareerCup

maxweight(currNode)
{
if (currNode.weight > maxWeight(left)+maxWeight(right))
return currNode.weight;
else
return maxWeight(left)+maxWeight(right);

}

Its not clear can you explain it lil bit

??? Can you please elaborate the question

What is the problem?

You have to output the set of nodes with the maximum weight. THe set has the constraint that if a node is in the set, its children aren't there in the set.


For eg:

1
   / \
  2   3
 /\    \
4  5    6
         \
          100
         

The set is {3,100,4,5}

are sure its just the children of a node that should not be there? i mean can grandchildren of the node still be there?
i was confused by the line "if a node is in the subset, NONE of its children can be in that subset."

the example stated above must hav ( 5, 100) as the answer according to the conditions given

use DP in TREE
maintain two values at each node dp[node][0],dp[node][1]
dp[node][0] maximum value that can be achieved without using this node
dp[node][1] maximum valus that can be achieved using this node.
try to compute the values of parent using the values of children.

if (p == NULL) return 0;
MaxTillNode p = max (MaxTill (children with out using the chilreen) + p->data, MaxTill(with using the children))

/*

A binary tree is given with a positive weight attached to each node. 
Find the subset of nodes in the tree whose sum give you the maximum weight such that if a node is in the subset, 
none of its children can be in that subset.

*/

class BTNode
{
public:
    BTNode(int w):weight(w), loss(0), left(null), right(null) {}

    void MarkLoss()
    {
        int lloss=0, rloss=0;
        if(left)
        {
            left->MarkLoss();
            lloss = left->GetLoss();
        }
        if(right)
        {
            right->MarkLoss();
            rloss = right->GetLoss();
        }
        if(rloss+lloss < weight)
        {
            loss = weight - (rloss+lloss);
            if(left) left->ForceLoss(0); //check for null
            if(right) right->ForceLoss(0);//check for null
        }

    }

    int GetLoss() { return loss; }

    void ForceLoss(int l) { loss = l; }

    void GetChildrenCausingLoss(vector<BTNode*>& list)
    {
        if(left)
            left->GetChildrenCausingLoss(list);
        if(right)
            right->GetChildrenCausingLoss(list);
        if(loss > 0)
            list.push_back(this);
    }

private:
    int weight;
    int loss;
    BST* left;
    BST* right;
};

int main()
{
    BTNode* root = CreateBT();

    root->MarkLoss();
    vector<BTNode*> max_weigh_list;
    root->GetChildrenCausingLoss(max_weigh_list);

    return 0;
}

Here is the solution of this problem :

private static int getMaxWeight(Node root) {

        int a = 0;
        int b = 0;

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

        if (root.left != null) {
            a = getMaxWeight(root.left.left) + getMaxWeight(root.left.right);
        }

        if (root.right != null) {
            b = getMaxWeight(root.right.left) + getMaxWeight(root.right.right);
        }


        int x = root.val + a + b;
        int y = getMaxWeight(root.left) + getMaxWeight(root.right);

        if (x >= y) {
            return x;
        } else {
            return y;
        }

    }

Solve(root) = MAX { (1 + sum of Solve for all grandchildren of root),
(sum of Solve for all children of root) }

Solve the problem recursively..

This is a typical maximum subset sum problem. We can start as follows first we find all the sums of a specific level and put it in an array..
so for example A[]={2,7,6,9....}..where A[0]->sum of nodes at level 0 A[1]->sum of nodes at level1.
After this we will use DP to find the max subsetsum of A[] with a constraint that no to consecutive element can be in that subset.