Add all larger values ​​in the given binary search tree to each node

BST or Binary Search Tree is a form of binary tree in which the value of all left nodes is less than the value of the root node and the value of all right nodes is greater than the value of the root node. For this problem, we will take a binary tree and add to it all values ​​greater than the current node value. The problem "add all larger values ​​to each node of a BST" is simplified to, for a BST, add all node values ​​larger than the current node value to that node value.

Add all larger values ​​to each node in BST Problem Statement:

Given a Binary Search Tree (BST), we need to add all larger values ​​to each node The sum of nodes.

Input

    10
    /  \
   /    \
  5     20
 / \   / \
1   7   1  5

Output

      70
    /   \
   82   45
  / \   / \
83 77  60 25

Explanation

This program will convert a binary search tree into a binary tree where the node values ​​are all The sum of the large elements plus the original value of the node.

Add all larger values ​​to each node in the binary search tree solution:

We use reverse inorder traversal (recursively calling the right subtree first instead of the left subtree ), and maintains a variable to store the sum of nodes traversed so far.

We then use this sum to modify the value of the current node, first adding its value to the sum, and then replacing the node's value with this sum.

Example

#include <iostream >
using namespace std;
struct node {
   int data;
   node *left;
   node *right;
};
node *newNode(int key) {
   node *temp=new node;
   temp->left=NULL;
   temp->right=NULL;
   temp->data=key;
   return temp;
}
void Inorder(node *root) {
   if(!root)
      return;
   Inorder(root->left);
   cout<<root->data<<" ";
   Inorder(root->right);
}
node *Insert(node *root,int key) {
   if(!root)
      return newNode(key);
   if(key<root->data)
      root->left=Insert(root->left,key);
   else
      root->right=Insert(root->right,key);
   return root;
}
void RevInorderAdd(node *root,int &sum) {
   if(!root)
      return;
   RevInorderAdd(root->right,sum);
   sum+=root->data;
   root->data=sum;
   RevInorderAdd(root->left,sum);
}
void AddGreater(node *root) {
   int sum=0;
   RevInorderAdd(root,sum);
}
int main() {
   /* Let us create following BST
      10
      / \
     5   20
    / \  / \
  1  7 15 25 */
   node *root = NULL;
   root = Insert(root, 10);
   Insert(root, 20);
   Insert(root, 25);
   Insert(root, 15);
   Insert(root, 5);
   Insert(root, 7);
   Insert(root, 1);
   Inorder(root);
   cout<<endl;
   AddGreater(root);
   Inorder(root);
   cout<<endl;
   return 0;
}

The above is the detailed content of Add all larger values ​​in the given binary search tree to each node. For more information, please follow other related articles on the PHP Chinese website!