REPLACE WITH SUM OF GREATER NODES

#1

Please tell me the approach of doing this question?

#2

hello @CODER_JATIN

do reverse Inorder traversal and keep track of the sum of all nodes visited so far, and we add this sum to every node.

void sumOfGreaterElements(node *root, int &sum)
{
    if (root == NULL)
        return;
    sumOfGreaterElements(root->right, sum);
    sum += root->data;
    root->data = sum;
    sumOfGreaterElements(root->left, sum);
}

we are doing reverse inorder because we want to traverse nodes in decreasing order

#3

aur bhaiya agar BST na hota , sirf BT hota tab ?

#4

tab to hame har node ke liye , pura tree traverse karna padta .
aur uski time complexity O(N^2) hogi phir

#5

hmm, kar to iske liye bhi kar skte hai lekin fir vhi complexity bd jayegi naa?

#6

ha … . . . . . . . . . . . . .

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.