প্রদত্ত BST-এর প্রতিটি নোডে সমস্ত বড় মান যোগ করুন

এখানে আমরা একটি আকর্ষণীয় সমস্যা দেখতে পাব, যেখানে আমরা একটি প্রদত্ত বাইনারি অনুসন্ধান গাছের প্রতিটি নোডে আরও বেশি মান যুক্ত করব। সুতরাং প্রাথমিক এবং শেষ গাছটি নীচের মত হবে −

অ্যালগরিদম

bstUpdate(root, sum) -

Begin
   if root is null, then stop
   bstUpdate(right of room, sum)
   sum := sum + value of root
   update root value using sum
   bstUpdate(left of room, sum)
End

উদাহরণ

#include<iostream>
using namespace std;
class Node {
   public:
      int data;
      Node *left, *right;
   };
   Node *getNode(int item) {
      Node *newNode = new Node();
      newNode->data = item;
      newNode->left = newNode->right = NULL;
      return newNode;
}
void updateBST(Node *root, int *sum) {
   if (root == NULL)
      return;
   updateBST(root->right, sum); //update right sub tree
   *sum = *sum + root->data;
   root->data = *sum; //update root data
   updateBST(root->left, sum); //update left sub tree
}
void BSTUpdate(Node *root) {
   int sum = 0;
   updateBST(root, &sum);
}
void inorder(Node *root) {
   if (root != NULL) {
      inorder(root->left);
      cout<<root->data<<" ";
      inorder(root->right);
   }
}
Node* insert(Node* node, int data) {
   if (node == NULL)
      return getNode(data);
   if (data <= node->data) //go to left
      node->left = insert(node->left, data);
   else //go to right
      node->right = insert(node->right, data);
   return node;
}
int main() {
   int data[] = {50, 30, 20, 40, 70, 60, 80};
   int n = sizeof(data)/sizeof(data[0]);
   Node *root = NULL;
   for(int i = 0; i < n; i++) {
      root = insert(root, data[i]);
   }
   BSTUpdate(root);
   inorder(root);
}

আউটপুট

350 330 300 260 210 150 80