Home »
Data Structure
Convert given Binary Search Tree to a Smaller Sum Tree
In this article, we are going to see how to convert a given Binary search tree to a smaller sum tree?
Submitted by Radib Kar, on October 13, 2020
Prerequisite: Convert given binary tree to a greater sum tree
In the previous article, we discussed on converting a binary search tree to a greater sum tree. Tn this article, we are going to see how we can convert a binary search tree into a smaller sum tree which is pretty much reverse of what we did earlier. Still, before discussing the solution, let’s understand what does mean by a smaller sum tree. A Smaller sum tree means the root will have value the same as the sum of the nodes having value less than the root. Let's discuss that with an example.
Below is the binary tree to be considered:
For example, the leftmost node 4 doesn't have any value less than this, so that will be replaced by 0. On the other has node 9 has nodes 4 & 7 less than that, so that will be replaced by 4+7=11. If we continue this way the resulting subtree will be:
Solution:
Of course, there is a naïve way, where for each node we can find which nodes are smaller than this and can replace the node value with the sum of the less valued nodes. That will take O(n^2) time complexity and will be similar for the binary tree as well. But we can have a better one pass solution using the properties of the binary search tree as we showed in our previous article to convert into a greater sum tree. Here, we need to visit the nodes in sorted order(ascending) and thus we need inorder traversal. And we can use inorder traversal to solve. The algorithm is like below:
 Have a variable sum which will store sum while the inorder traversal. Initiate sum to 0

Do inorder traversal like below:

// Base case
if the root is NULL
return;
 Recur for the left subtree first as it's a normal inorder traversal
 store the current sum to variable previous sum and update sum as sum+ root value
change the root value as previous sum which is the sum of the nodes already traversed and those are surely less than the node since they fall in the left subtree only
 Recur for the right subtree now
Below is the implementation of the above algorithm
#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
Dry run
Below is the step by step dry run of the above implementation. Since it's a reverse inorder traversal, it will first reach the rightmost node.
Initially, sum is 0 so that will be transferred to the leftmost node via prevsum and the sum updated as sum+root>val=0+4=4
Now, sum is 4 so that will be transferred to the current node via prevsum and the sum updated as sum+root>val=4+7=11
You can check that 4 is the only smaller node than 7
Now, sum is 11 so that will be transferred to the current node via prevsum and the sum updated as sum+root>val=11+9=20
You can check that 4 & 7(total 11) are the only smaller node than 9
Now, sum is 20 so that will be transferred to the current node via prevsum and the sum updated as sum+root>val=20+10=30
You can check that 4, 7, 9(total 20) are the smaller nodes than 10
Similarly,
Finally, the smaller sum tree is:
TOP Interview Coding Problems/Challenges