1.
Introduction đźĄł
2.
Problem Statement đź§ľ
2.1.
Sample Examples
3.
Approach #1đź§‘â€Ťđź’»
3.1.
Algorithm
3.2.
Implementation in C++
3.2.1.
Time Complexity âŚ›
3.2.2.
Space Complexity đźš€
4.
Approach #2đź§‘â€Ťđź’»
4.1.
Pseudocode
4.2.
Implementation in C++
4.2.1.
Time Complexity âŚ›
4.2.2.
Space Complexity đźš€
5.
5.1.
What is a binary tree?
5.2.
What are the benefits of a binary tree?
5.3.
What exactly is a perfect binary tree?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

# BST to a Tree with sum of all smaller keys

Harsh
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

## Introduction đźĄł

A tree in which every node can have at max 2 children is known as a binary tree and a BST is a variation of a binary tree in which all of the nodes present in the left subtree are smaller than the root node and all of the nodes present in the right side of the root node are greater than the root node.

In this article, we will solve a coding problem related to the BST in which we have to convert a BST into a binary tree with a small condition.

## Problem Statement đź§ľ

Ninja has given you a BST. Your task is to convert the given BST into a tree such that every node in the resultant binary tree is the sum of all smaller nodes in the original BST plus the node itself.

To better understand the question, let's look at an example.

### Sample Examples

Input

Output

Explanation

As seen in the photo up top. The value of the current node is calculated by adding the sum of all the smaller values plus the current nodeâ€™s value. This process is repeated for all the nodes present in the BST. Hence, we get 5 15 27 47 72 112 157 as our result.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## 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

1. Traverse the given BST.

2. For each node, again traverse the tree in and find the sum of all the smaller nodes.

3. Store this sum into an array.

4. 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;
}``````

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;
}``````

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

### 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 TreesBinary search treeDeletion in Binary Search TreeUnique 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!

Live masterclass