consider the following BST.
45 / \ 30 60 / \ / \ 10 35 50 80 The above tree should be modified to following 235 / \ 300 140 / \ / \ 310 270 190 80 This can be done in one traversal.This can be achieved by doing reverse Inorder traversal ,keep track of some of all visited nodes.
struct node{ int data; struct node *left, *right;};// A utility function to create a new BST nodestruct node *newNode(int item){ struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->data = item; temp->left = temp->right = NULL; return temp;}// Recursive function to add all greater values in every nodevoid modifyBSTUtil(struct node *root, int *sum){ // Base Case if (root == NULL) return; // Recur for right subtree modifyBSTUtil(root->right, sum); // Now *sum has sum of nodes in right subtree, add // root->data to sum and update root->data *sum = *sum + root->data; root->data = *sum; // Recur for left subtree modifyBSTUtil(root->left, sum);}// A utility function to do inorder traversal of BSTvoid inorderTraversal(struct node *root){ if (root != NULL) { inorderTraversal(root->left); printf("%d ", root->data); inorderTraversal(root->right); }}// Driver Program to test above functionsint main(){ struct node *root = NULL; /// add values here
<code class="cpp spaces"> int sum = 0; modifyBSTUtil(root, &sum); // print inoder tarversal of the modified BST inorderTraversal(root); return 0;}Resolving technical problems:
Solve your technical problems instantly
We provide Remote Technical Support from Monday to Sunday, 7:00PM to 1:00 AM
Mail your problem details at [email protected] along with your mobile numberand we will give you a call for further details. We usually attend your problems within 60 minutes and solve it in maximum 2 days.