This is how i approached this problem(all test cases passed). But Time Comp. is O(n^2). Is there a better approach for this problem?
#include<iostream>
using namespace std;
class node{
public:
int data;
node *left;
node *right;
// constructor
node(int d){
data = d;
left = NULL;
right = NULL;
}
};
node *buildTree(int in[], int s, int e){
// base case
if(s>e){
return NULL;
}
// rec case
int mid = (s+e)/2;
node *root = new node(in[mid]);
root->left = buildTree(in,s,mid-1);
root->right = buildTree(in,mid+1,e);
return root;
}
void print(node *root){
// base case
if(!root){
return;
}
// rec case
cout<<root->data<<" ";
print(root->left);
print(root->right);
}
int main(){
int n;
cin>>n;
int in[1000];
for(int i=0; i<n; i++){
cin>>in[i];
}
int arr[1000];
int sum = 0;
// replacing each node with sum of its greater nodes
for(int i=0; i<n; i++){
for(int j=i; j<n; j++){
sum += in[j];
}
arr[i] = sum;
sum = 0;
}
node *root = buildTree(arr,0,n-1);
print(root);
return 0;
}