Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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.
Frequently Asked Questions
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

Author 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. 

Introductory image

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

Input

 

Output

Output

 

Explanation

Explaination

 

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

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

Previous article
Node with minimum value in a BST
Next article
Count the number of Nodes having Special Two-digit Numbers in BST
Live masterclass