Convert a BST to a Binary Tree such that the sum of all greater elements is added to every element

Method 1: Brute Force

The basic idea to solve this problem is to find the sum of values of all the nodes greater than this node for each node and add it to the value of the current node.

Algorithm

• Start traversing the BST in inorder form.
• For each node, traverse the whole tree again in in-order form.
• Create an array and store the sum in that array.
• Traverse the tree in inorder form and increment the value of every node with its corresponding sum value in the array.

C++ code

#include <bits/stdc++.h>
using namespace std; 
class Node { 
    public: 
    int data; 
    Node *left; 
    Node *right; 
    
    Node(int data) { 
        this->data = data; 
        left = right = NULL; 
    } 
}; 
void preOrder(Node *root) { 
    if (root != NULL) { 
        cout<<root->data<<" "; 
        preOrder(root->left); 
        preOrder(root->right); 
    } 
} 
int findSum(Node *root, int value) { 
    // if root is null, sum is 0 
    if (root == NULL) { 
        return 0; 
    } 
    
    // initialise sum as 0 
    int sum = 0; 
    
    // start traversing the tree and find the sum of all the elements greater than that element
    queue<Node*> q; 
    q.push(root); 
    while (!q.empty()) { 
        Node *current = q.front(); 
        q.pop(); 
        if (current->data > value) { 
            sum += current->data; 
        } 
        if (current->left != NULL) { 
            q.push(current->left); 
        } 
        if (current->right != NULL) { 
            q.push(current->right); 
        } 
    } 
    
    return sum; 
} 
void populateSum(Node *root, Node *curr, vector<int> &SumVector) { 
    // traverse the tree and for each node calculate the 
    // sum of elements greater than it 
    if (curr != NULL) { 
        populateSum(root, curr->left, SumVector); 
        
        // Check for all the tree nodes to find the sum 
        int sum = findSum(root, curr->data); 
        SumVector.push_back(sum); 
        populateSum(root, curr->right, SumVector); 
    } 
} 
void addGreater(Node *root, vector<int> &SumVector) { 
    // traverse the tree and for each node 
    // replace its value with the corresponding sum 
    if (root != NULL) { 
        addGreater(root->left, SumVector); 
        // change this value 
        root->data += SumVector[0]; 
        SumVector.erase(SumVector.begin()); 
        addGreater(root->right, SumVector); 
    } 
} 
int main() { 
    // Example 1 Tree 
    Node *root = new Node(4); 
    root->left = new Node(2); 
    root->right = new Node(6); 
    root->left->left = new Node(1); 
    root->left->right = new Node(3); 
    root->right->left = new Node(5); 
    root->right->right = new Node(7); 
    
    vector<int> SumVector; 
    populateSum(root, root, SumVector); 
    
    addGreater(root, SumVector); 
    preOrder(root); 
    cout<<endl; 
    
    return 0; 
}

You can also try this code with Online C++ Compiler

Run Code

Output: 

22 27 28 25 13 18 7 

You can also try this code with Online C++ Compiler

Run Code

JAVA Code

import java.util.*;
   // class for the node of a binary tree
public class ConvertABSTToABinaryTree {
      static class Node {
        int data;
        Node left, right;
        public Node(int d) {
            this.data = d;
        }
    }
    
    // function to print 
//preorder traversal of a binary tree
    private static void printPreOrder(Node root) {
        if (root != null) {
            System.out.print(root.data + " ");
            printPreOrder(root.left);
            printPreOrder(root.right);
        }
    }
    
    
//function to find the sum
    private static int findSum(Node root, int value) {
         // return 0 if root is null.
        if (root == null) {
            return 0;
        }
        // initialise sum as 0
        int sum;
        sum = 0;
        // traverse the tree in inorder and find the sum of all the values greater than that value
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node curr = queue.poll();
            if (curr.data > value) {
                sum += curr.data;
            }
            if (curr.left != null)
                queue.add(curr.left);
            if (curr.right != null)
                queue.add(curr.right);
        }
        // return sum
        return sum;
    }
    
    private static void populateSum(Node root, Node curr, ArrayList<Integer> sumList) {
        // traverse the tree and for each node calculate the sum
        // of elements greater than it
        if (curr != null) {
            populateSum(root, curr.left, sumList);
            // traverse all the nodes to find the sum
            int sum = findSum(root, curr.data);
            sumList.add(sum);
            populateSum(root, curr.right, sumList);
        }
    }
    
    private static void  addGreater(Node root, ArrayList<Integer> sumList) {
        // traverse the tree and for each node
        // increment its value by sum
        if (root != null) {
            addGreater(root.left, sumList);
            // increment this value
            root.data += sumList.get(0);
            sumList.remove(0);
            addGreater(root.right, sumList);
        }
    }
    
    public static void main(String[] args) {
        // Example Tree
        Node root = new Node(4);
        root.left = new Node(2);
        root.right = new Node(6);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        root.right.left = new Node(5);
        root.right.right =  new Node(7);
        ArrayList<Integer> sumList = new ArrayList<>();
        populateSum(root, root, sumList);
        addGreater(root, sumList);
        printPreOrder(root);
        System.out.println();
    }
}

You can also try this code with Online Java Compiler

Run Code

Output: 

22 27 28 25 13 18 7 

You can also try this code with Online Java Compiler

Run Code

Complexity Analysis

Time Complexity: O(N^2), N is the number of nodes in the BST. For each node, we are traversing the whole tree again.

Space Complexity: O(h), h is the tree's height. O(h) space for the recursion call stack.

We are taking a lot of time in this approach. For each node, we are again traversing each node, which seems like a lot of repetitive work. Can we do better? Can we use any property of BST to solve this problem?💡

For answers, Keep reading.

Must Read Difference between ArrayList and LinkedList

Method 2: Using the property of BST.

We know that BST is a special type of tree. It has some properties like: 

1. For a node, all the nodes in the left subtree have values less than the current node's value.
2. For a node, all the nodes in the right subtree have values greater than the current node's value.
3. The left and right subtree should also be binary search trees and follow all three properties.

Now, if each node in the left subtree has lesser value nodes and each node in the right subtree has greater value nodes, we can say that the in-order traversal of the BST is always sorted.

We can use this property to convert BST to a binary tree such that the sum of all greater elements is added to every element.

Algorithm

• We will traverse in reverse in order to traverse greater value nodes first. 
• We will declare a variable called sum to keep track of the sum of all nodes visited so far. 
• Let this variable be the sum. For each node currently being visited, first add the value of this node to sum, i.e. sum = sum + node->value. Then change the current node's value to sum, i.e., node->value = sum. 
• When we traverse a BST in reverse order, all nodes already visited have greater values for every element currently being visited.

C++ Code

// Program to change a 
 //BST to Binary Tree
// such that the value of a node becomes 
// current value plus the sum of all greater value elements in BST
#include <bits/stdc++.h>
using namespace std;


//declaring node of BST
class node { 
    public: 
    int value; 
    node *left; 
    node *right; 
    
    node(int data) { 
        this->value = data; 
        left = right = NULL; 
    } 
}; 



// A recursive function that traverses the
// given BST in reverse inorder and for
// every value adds all greater values to it
void addGreaterUtil(struct node *root, int *sum)
{
  // Base Case
  if (root == NULL)
  return;


// Calling recursion first for right subtree
// so that sum of all greater elements is stored at sum


  addGreaterUtil(root->right, sum);
  // Update the value at sum
  *sum= *sum + root->value;


  // Update value of this node
  root->value = *sum;
 

  // Recur for left subtree so that the
 // updated sum is added to smaller nodes
  addGreaterUtil(root->left, sum);
}


// A wrapper over addGreaterUtil(). It initialises
// sum and calls addGreaterUtil() to recursively
// update and use value of sum
void addGreater(struct node *root)
{
  int sum = 0;
  addGreaterUtil(root, &sum);
}


// A function to print inorder
// traversal of Binary Tree
void printInorder(struct node* node)
{
  if (node == NULL)
  return;
  printInorder(node->left);
  cout << node->value << " " ;
  printInorder(node->right);
}



int main()
{
    node *root = new node(4); 
    root->left = new node(2); 
    root->right = new node(6); 
    root->left->left = new node(1); 
    root->left->right = new node(3); 
    root->right->left = new node(5); 
    root->right->right = new node(7); 


    addGreater(root);
    cout << endl;
    printInorder(root);


  return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output: 

28 27 25 22 18 13 7 

You can also try this code with Online C++ Compiler

Run Code

JAVA Code

// Program to change a 
//BST to Binary Tree
// such that the value of a node becomes 
// current value plus the sum of all greater value elements in BST



class Node {

  int value;
  Node left, right;


Node(int d) {
  value = d;
  left = null;
  right = null;

 }
}


class Sum {

  int sum = 0;
}


class BinaryTree {
  static Node root;
  Sum sum = new Sum();


  // A function that traverses  recursively 
  //  given BST in reverse inorder. For every key, 
  // it adds all greater values to element
void addGreaterUntil(Node node, Sum sum) {

  // Base Case
  if (node == null) {
  return;
  }


// call recursion for right subtree first
//so that sum of all greater
// nodes is stored in sum
 addGreaterUntil(node.right, sum);


 // Update the value at sum
 sum.sum = sum.sum + node.value;


 // Update value of this node
 node.value = sum.sum;


  // calling recursion for left subtree 
  //it adds the updated sum to smaller valued nodes
  addGreaterUntil(node.left, sum);
}


// A wrapper function over addGreaterUntil()
//It initialises sum and calls addGreaterUntil() 
//to update and use value of sum recursively
 Node addGreater(Node node) {
  addGreaterUntil(node, sum);
  return node;
 }


// function to print inorder traversal of the given Binary Tree
void printInorder(Node node) {
  if (node == null)return;

  //calling for left subtree
  printInorder(node.left);
  System.out.print(node.value + " ");
   //calling for right subtree
  printInorder(node.right);
}


// Driver program to test the above functions
public static void main(String[] args) {
  BinaryTree tree = new BinaryTree();
  tree.root = new Node(4);
        tree.root.left = new Node(2);
        tree.root.right = new Node(6);
        tree.root.left.left = new Node(1);
        tree.root.left.right = new Node(3);
        tree.root.right.left = new Node(5);
        tree.root.right.right =  new Node(7);


Node node = tree.addGreater(root);
 tree.printInorder(node);
 }
}

You can also try this code with Online Java Compiler

Run Code

Output: 

28 27 25 22 18 13 7 

You can also try this code with Online Java Compiler

Run Code

Complexity Analysis

Time Complexity: O(N), N is the number of nodes in the BST. We are traversing all nodes only once.  

Space Complexity: O(h), h is the tree's height. O(h) space for the recursion call stack.

Frequently Asked Questions

What is a Binary Tree?

As the name suggests, Binary means two, i.e, a tree node is allowed to have a maximum of two children.

What is a BST?

BST (Binary Search Tree) is a special type of is a node-based binary tree data structure. It follows properties like: 

1. For a node, all the nodes in the left subtree have values less than the current node's value.
2. For a node, all the nodes in the right subtree have values greater than the current node's value.
3. The left and right subtree should also be binary search trees and follow all three properties.

What is the most efficient way to convert a BST into a binary tree such that the sum of all greater keys is added to every key?

There are multiple ways to do this. One efficient method is to use the property of BST.

All the nodes in the left subtree have values less than the current node's value.

All the nodes in the right subtree have values greater than the current node's value.

Conclusion

In this blog, we learned the various methods to solve the popular interview question Convert a BST to a Binary Tree such that the sum of all greater keys is added to every key. We learned the most logical sequence from brute force to the optimal solution. I hope you enjoyed reading our blog on ‘Convert a BST to a Binary Tree such that the sum of all greater keys is added to every key.

Recommended problems -

• Leaf Nodes in Binary Tree
• Vertical Order Traversal of a Binary Tree
• Binary Array Sorting
• Boundary Traversal Of Binary Tree

Refer to our Guided Path on Coding Ninjas Studio to upskill ourselves in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, Machine learning, and many more! But suppose we have just started our learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, we must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, we may consider our paid courses to give our career an edge over others!

Do upvote this blog if you find it helpful and engaging!

Happy Learning!!