Approach #1🧑💻
To convert a BST to a tree with the sum of all smaller values, we can do the following:
First, we can traverse the tree in any order. Then, for each node, traverse the entire tree once again to get the sum of all the nodes that are smaller than it. Keep track of this total for each node in the array, then raise the value of each node's corresponding total.
Algorithm
-
Traverse the given BST.
-
For each node, again traverse the tree in and find the sum of all the smaller nodes.
-
Store this sum into an array.
- After storing once again traverse the tree using the order used in step 1 and increment every node with its corresponding sum in the array.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
int data;
Node *left, *right;
Node(int val)
{
data = val;
left = right = nullptr;
}
};
// function to print the inorder traversal of tree
void printInorder(Node *node)
{
if (node == NULL)
return;
printInorder(node->left);
cout << node->data << ' ';
printInorder(node->right);
}
int findSumOfSmaller(Node *root, int greaterVal)
{
// if root is null return 0
if (!root)
return 0;
int sum = 0;
// creating a queue to find the sum of all smaller values than 'greaterVal'
queue<Node *> q;
// pushing the root node
q.push(root);
// traversing the tree
while (!q.empty())
{
Node *current = q.front();
q.pop();
// add the value of current node to the sum
// if it's smaller than the \greaterVal'
if (current->data < greaterVal)
{
sum += current->data;
}
// going to left and right sub tree
if (current->left)
q.push(current->left);
if (current->right)
q.push(current->right);
}
return sum;
}
// function to make list of sum of all the smaller values in our tree
void buildList(Node *root, Node *curr, vector<int> &list)
{
// if curr is not null generate list
if (curr)
{
// traversing the tree and adding the sum of all smaller keys
// into the list
buildList(root, curr->left, list);
int sum = findSumOfSmaller(root, curr->data);
list.push_back(sum);
buildList(root, curr->right, list);
}
}
void convertToTree(Node *root, vector<int> &list)
{
// base case
if (root == nullptr)
return;
// traversing the tree and adding the value of smaller keys into current node
convertToTree(root->left, list);
root->data += list[0];
list.erase(list.begin());
convertToTree(root->right, list);
}
int main()
{
// creating binary search tree
Node *root = new Node(20);
root->left = new Node(10);
root->right = new Node(40);
root->left->left = new Node(5);
root->left->right = new Node(12);
root->right->left = new Node(25);
root->right->right = new Node(45);
// print the tree before converting
cout << "Before converting: ";
printInorder(root);
cout << endl;
// creating a list to store the sum of all smaller values
vector<int> list;
// filling the list
buildList(root, root, list);
// converting the tree
convertToTree(root, list);
// print the tree after converting.
cout << "After Converting: ";
printInorder(root);
cout << endl;
return 0;
}
You can also try this code with Online C++ Compiler
Output
Before converting: 5 10 12 20 25 40 45
After converting: 5 15 27 47 72 112 157
Time Complexity ⌛
As we are traversing the tree and while traversing at each node we again traverse the whole tree to find the sum of smaller values that is why the time complexity of our program is O(N^2), Where N is the number of nodes present in our BST.
Space Complexity 🚀
The space complexity of the above program is O(h), where h is the height of our BST. It is because we are using the queue while finding the sum of all smaller values in our BST and at any point of time the maximum number of elements in our queue would be equal to the height of our BST.
Approach #2🧑💻
Nodes present in the left subtree of the BST are smaller than the root node. So, by doing inorder traversal we can traverse the BST in increasing order due to this we will visit all of the smaller nodes first. Hence, we can find the sum of all the smaller nodes and add it to the current node.
Pseudocode
CONVERT (ROOT, SUM):
if ROOT is NULL
return;
CONVERT(ROOT->left, SUM)
SUM = SUM + ROOT->data
ROOT->data = SUM
CONVERT(ROOT->right, SUM);
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
int data;
Node *left, *right;
Node(int val){
data = val;
left = right = nullptr;
}
};
void convertToTree(struct Node* root, int &sum) {
// Base Case
if (root == NULL)
return;
// storing sum of all smaller nodes by
// visiting the left subtree first
convertToTree(root->left, sum);
// updating sum
sum = sum + root->data;
// changing the value of current node
root->data = sum;
// updating right subtree
convertToTree(root->right, sum);
}
Node *insertData(Node *root, int data) {
// tree is empty, return new node
if (root == nullptr) return new Node(data);
// recur the tree to find the position where
// data needs to be inserted
if (data < root->data) root->left = insertData(root->left, data);
else if (data > root->data) root->right = insertData(root->right, data);
// return the root node
return root;
}
void printInorder(Node* node) {
if (node == NULL) return;
printInorder(node->left);
cout << node -> data << ' ';
printInorder(node->right);
}
int main(){
// creating binary search tree
Node *root = nullptr;
root = insertData(root, 20);
insertData(root, 10);
insertData(root, 5);
insertData(root, 12);
insertData(root, 11);
insertData(root, 40);
insertData(root, 25);
insertData(root, 45);
cout << "Before converting: ";
printInorder(root);
int sum = 0;
convertToTree(root, sum);
cout << "\nAfter converting: ";
printInorder(root);
cout << endl;
return 0;
}
You can also try this code with Online C++ Compiler
Output
Before converting: 5 10 12 20 25 40 45
After converting: 5 15 27 47 72 112 157
Time Complexity ⌛
We are traversing the tree only once. So, the time complexity will be O(n), where n is the number of nodes in our BST.
Space Complexity 🚀
The space complexity of the above approach is O(H) where H is the height of the input BST. This is because of the size of the recursion stack used in the implementation.
Check out this problem - Two Sum Problem
Frequently Asked Questions
What is a binary tree?
A binary tree is a tree data structure having a maximum of two children. There can only be two children per element in a binary tree, hence we usually refer to them as the left and right children.
What are the benefits of a binary tree?
The simplicity of binary trees is its key benefit. A straightforward structure for managing and organizing data is included in binary trees. Additionally, binary trees have the following advantages: They can be applied to reflect patterns in data.
What exactly is a perfect binary tree?
A perfect binary tree is a tree in which every node has two children or no children at all.
Conclusion
In this article, we have extensively discussed a coding problem in which we have to convert the BST tree into a binary tree such that all of the nodes in the original BST are changed to node plus the sum of all the smaller nodes. We have seen two different simple yet optimal solutions to solve the problem.
If you think this blog has helped you enhance your knowledge about the above question, and if you would like to learn more, check out our articles Balanced Binary Search Trees, Binary search tree, Deletion in Binary Search Tree, Unique Binary Search Trees, and many more on our website.
Visit our website to read more such blogs. Make sure that you enroll in the courses provided by us, take mock tests and solve problems available and interview puzzles. Also, you can pay attention to interview stuff- interview experiences and an interview bundle for placement preparations. Do upvote our blog to help fellow ninjas grow.
Please upvote our blog to help other ninjas grow.
Happy Learning!
24+ registered 
