#include <bits/stdc++.h>
using namespace std;

// tree node is defined
class TreeNode
{
public:
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        val = data;
        left = NULL;
        right = NULL;
    }
};

// inorder traversal for tree
void inorder(TreeNode *root)
{
    if (!root)
        return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

// Recursive function to transform a BST to smaller sum tree.
// do a inorder traversal for the BST
void transformToSmallerSumTreeRecur(TreeNode *root, int &sum)
{
    // Base case
    if (!root)
        return;

    // Recur for left subtree first since it's normal inorder traversal
    transformToSmallerSumTreeRecur(root->left, sum);

    // store the previous sum and update sum
    int prevSum = sum;
    sum = sum + root->val;

    // Store old sum in the current node which is sum of the left
    // subtree nodes(nodes lesser than the root)
    root->val = prevSum;

    // Recur for right subtree now
    transformToSmallerSumTreeRecur(root->right, sum);
}

void transformToSmallerSumTree(TreeNode *root)
{
    // initially sum is 0
    int sum = 0;
    transformToSmallerSumTreeRecur(root, sum);
}

int main()
{
    // Tree built as per example
    TreeNode *root = new TreeNode(10);
    root->left = new TreeNode(7);
    root->right = new TreeNode(15);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(9);
    root->right->left = new TreeNode(13);
    root->right->right = new TreeNode(18);

    cout << "Inorder Traversal of the given tree\n";
    inorder(root);
    cout << "\nconverting to smaller Sum tree\n";
    transformToSmallerSumTree(root);
    cout << "Conversion completed\n";
    cout << "Inorder Traversal of transformed smaller sum tree:\n";
    inorder(root);

    return 0;
}


Output 

Inorder Traversal of the given tree
4 7 9 10 13 15 18
converting to smaller Sum tree
Conversion completed
Inorder Traversal of transformed smaller sum tree:
0 4 11 20 30 43 58