@Dave : my code is not that complicated ...if you ignore the helper
function and check fillCup();
it just similar to preorder travesal and pour half to left and right child.
here is the explanation :-
node* fillCup(node *root,float pour,float capacity)
{
float temp;
if(root==NULL)
return NULL;
if(root->data+pour >= capacity)
{
if(root->data==0) // if cup is empty then fill cup to full and
reduce pour value for the next level
{
root->data=capacity;
pour=pour-capacity;
}
else
{
// if there is alreday some water in the cup , then it will
fill the cup and reduce pour =pour - empty volume in partially filled cup.
temp=capacity-(root->data);
root->data=capacity;
pour=pour-temp;
if(pour==0)
{
return root;
}
}
}
else
{
// this is for the part where overflow will never happen , even
after adding the poured quantity to the cup.
root->data+=pour;
return root;
}
fillCup(root->left,pour/2,capacity); // pour 1/2 to the left
fillCup(root->right,pour/2,capacity); // pour 1/2 to the right
}
Time complexity = O(n).
your approach is nice but it O(n^2) .
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
