Friday, May 4, 2012

Given a BST, convert it so that each node has value equal to sum of all the nodes (including itself) which are greater than that node in the whole tree.


1 comment :

Shwetank said...

It seems to me very direct question.
Correct me if my logic is going wrong:
In the below function 'ptr' is the root of BST, while *sum == 0;

void move_right_left(treeptr ptr, int *sum) {
.......if(ptr) {
.......move_right_left(ptr->left);
.......ptr>data = ptr->data + *sum;
.......*sum = ptr->data;
.......move_right_left(ptr->right);
.......}
}

Logic is to traverse the BST in the fashio R-V-L while updating the node values.