//Given an arbitrary binary tree, convert it to a binary tree that holds
//Children Sum Property. You can only increment data values in any node
//(You cannot change structure of tree and cannot decrement value of any node).
//             50
//           /     \
//         /         \
//       7             2
//     / \             /\
//   /     \          /   \
//  3        5      1      30

#include<iostream>
using namespace std;

class tree
{
    public:
           int data;
           class tree* left;
           class tree* right;
           tree(int data)
           {
               this->data = data;
               left = NULL;
               right = NULL;
           }
};

void insert(class tree** root, int data)
{
    if(!*root)
    {
        *root = new tree(data);
        return;
    }
    else if((*root)->data > data)
        insert(&(*root)->left, data);
    else
        insert(&(*root)->right, data);
}

void traverseUpToDown(class tree* root)
{
    if(!root || (!root->left && !root->right))
        return;
    int diff = 0;
    diff = root->data - (((root->left)?(root->left->data):0) + ((root->right)?(root->right->data):0));

    if(diff > 0)
    {
        if(root->left)
            root->left->data += diff;
        else
            root->right->data += diff;
    }
    traverseUpToDown(root->left);
    traverseUpToDown(root->right);
}

void traverseDownToUp(class tree* root)
{
    if(!root || (!root->left && !root->right))
        return;
    traverseDownToUp(root->left);
    traverseDownToUp(root->right);
    int diff = 0;
    diff = root->data - (((root->left)?(root->left->data):0) + ((root->right)?(root->right->data):0));
    if(diff < 0)
        root->data += -1*diff;
}

void convertToChildrenSumProperty(class tree* root)  // will be doing two traversals
{
    traverseDownToUp(root);  //first convert to required property from bottom up manner.
    traverseUpToDown(root);  // now from top to bottom.
}

void display(class tree* root)
{
    if(root)
    {
        display(root->left);
        cout<<"  "<<root->data;
        display(root->right);
    }
}

int main()
{

    class tree* root = new tree(50);
    root->left = new tree(7);
    root->right = new tree(2);
    root->left->left = new tree(3);
    root->left->right = new tree(5);
    root->right->left = new tree(1);
    root->right->right = new tree(30);

    display(root);
    cout<<endl;

    convertToChildrenSumProperty(root);
    display(root);
    cout<<endl;

    system("PAUSE");
    return 0;
}