Binary Search Trees : Interview Question

Question : In a BST to every element add sum of elements greater than it.

Answer: The first thing is to notice that on doing this the resulting tree would be the reverse of the binary search tree. Implementing this  you should notice that the inorder travesal prints the elements in increasing order.Hence we need to modify the inorder traversal a bit to do this.Here is a sample C++/C code for insert and inorder for a BST.

#include<iostream>
#include<cstdlib>

using namespace std;

struct node
{
    int data;
    struct node *parent;
    struct node *left;
    struct node *right;
}*root;

typedef struct node node;

/**
*Makes a new node from the integer
*value and returns a pointer to the
*new created node
*/
node* makeNode(int num)
{
    node *temp=(node*)malloc(sizeof(node));
    temp->data=num;
    temp->right=NULL;
    temp->left=NULL;
    return temp;
}

/**
 * Inserting a node in a BST
 */
void insert(int num,node *T)
{
    if(T==NULL)
    root=makeNode(num);
    else
    {
        if(T->data>num)
        {
            if(T->left==NULL)
            T->left=makeNode(num);
            else
            insert(num,T->left);
        }
        else
        {
            if(T->right==NULL)
            T->right=makeNode(num);
            else
            insert(num,T->right);
        }
    }
}

/**
*Inorder traversal of the tree
*/
void inorder(node* T)
{
    if(T!=NULL)
    {
        inorder(T->left);
        cout<<T->data<<" ";
        inorder(T->right);
    }
}

Now to add the elements which are greater than a particular node we need to reverse the inorder by accessing the bigger elements i.e. right first and then the left. On accessing the right add the data to the data already collected and then change the node value accordingly.Hope you better understand by the code.

void chorder(node *T,int *data)
{
    if(T!=NULL)
    {
        chorder(T->right,data);
        *data+=T->data;
        T->data=*data;
        chorder(T->left,data);
    }
}

Notice that that data needs to be reference so that after being updated it is assigned to the other nodes.