Agregue todos los valores mayores a cada Node en un BST dado

Dado un árbol de búsqueda binario ( BST ), modifíquelo para que todos los valores mayores en el BST dado se agreguen a cada Node. Por ejemplo, considere el siguiente BST.

              50
           /      \
         30        70
        /   \      /  \
      20    40    60   80 

The above tree should be modified to following 

              260
           /      \
         330        150
        /   \       /  \
      350   300    210   80

Un método simple para resolver esto es encontrar la suma de todos los valores mayores para cada Node. Este método tomaría O (n ^ 2) tiempo.

C++

// C++ program to add all greater
// values in every node of BST
#include <bits/stdc++.h>
using namespace std;
 
class Node {
public:
    int data;
    Node *left, *right;
};
 
// A utility function to create
// a new BST node
Node* newNode(int item)
{
    Node* temp = new Node();
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}
 
// Recursive function to add all
// greater values in every node
void modifyBSTUtil(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 wrapper over modifyBSTUtil()
void modifyBST(Node* root)
{
    int sum = 0;
    modifyBSTUtil(root, &sum);
}
 
// A utility function to do
// inorder traversal of BST
void inorder(Node* root)
{
    if (root != NULL) {
        inorder(root->left);
        cout << root->data << " ";
        inorder(root->right);
    }
}
 
/* A utility function to insert
a new node with given data in BST */
Node* insert(Node* node, int data)
{
    /* If the tree is empty,
       return a new node */
    if (node == NULL)
        return newNode(data);
 
    /* Otherwise, recur down the tree */
    if (data <= node->data)
        node->left = insert(node->left, data);
    else
        node->right = insert(node->right, data);
 
    /* return the (unchanged) node pointer */
    return node;
}
 
// Driver code
int main()
{
    /* Let us create following BST
            50
        / \
        30 70
        / \ / \
    20 40 60 80 */
    Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);
 
    modifyBST(root);
 
    // print inorder traversal of the modified BST
    inorder(root);
 
    return 0;
}
 
// This code is contributed by rathbhupendra

C

// C program to add all greater
// values in every node of BST
#include <stdio.h>
#include <stdlib.h>
 
struct Node {
    int data;
    struct Node *left, *right;
};
 
// A utility function to create a new BST node
struct 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 node
void 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 wrapper over modifyBSTUtil()
void modifyBST(struct Node* root)
{
    int sum = 0;
    modifyBSTUtil(root, &sum);
}
 
// A utility function to do
// inorder traversal of BST
void inorder(struct Node* root)
{
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}
 
/* A utility function to insert
a new node with given data in BST */
struct Node* insert(
    struct Node* node, int data)
{
    /* If the tree is empty, return a new node */
    if (node == NULL)
        return newNode(data);
 
    /* Otherwise, recur down the tree */
    if (data <= node->data)
        node->left = insert(node->left, data);
    else
        node->right = insert(node->right, data);
 
    /* return the (unchanged) node pointer */
    return node;
}
 
// Driver Program to test above functions
int main()
{
    /* Let us create following BST
              50
           /     \
          30      70
         /  \    /  \
       20   40  60   80 */
    struct Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);
 
    modifyBST(root);
 
    // print inorder traversal of the modified BST
    inorder(root);
 
    return 0;
}

Java

// Java code to add all greater values to
// every node in a given BST
 
// A binary tree node
class Node {
 
    int data;
    Node left, right;
 
    Node(int d)
    {
        data = d;
        left = right = null;
    }
}
 
class BinarySearchTree {
 
    // Root of BST
    Node root;
 
    // Constructor
    BinarySearchTree()
    {
        root = null;
    }
 
    // Inorder traversal of the tree
    void inorder()
    {
        inorderUtil(this.root);
    }
 
    // Utility function for inorder traversal of
    // the tree
    void inorderUtil(Node node)
    {
        if (node == null)
            return;
 
        inorderUtil(node.left);
        System.out.print(node.data + " ");
        inorderUtil(node.right);
    }
 
    // adding new node
    public void insert(int data)
    {
        this.root = this.insertRec(this.root, data);
    }
 
    /* A utility function to insert a new node with
    given data in BST */
    Node insertRec(Node node, int data)
    {
        /* If the tree is empty, return a new node */
        if (node == null) {
            this.root = new Node(data);
            return this.root;
        }
 
        /* Otherwise, recur down the tree */
        if (data <= node.data) {
            node.left = this.insertRec(node.left, data);
        }
        else {
            node.right = this.insertRec(node.right, data);
        }
        return node;
    }
 
    // This class initialises the value of sum to 0
    public class Sum {
        int sum = 0;
    }
 
    // Recursive function to add all greater values in
    // every node
    void modifyBSTUtil(Node node, Sum S)
    {
        // Base Case
        if (node == null)
            return;
 
        // Recur for right subtree
        this.modifyBSTUtil(node.right, S);
 
        // Now *sum has sum of nodes in right subtree, add
        // root->data to sum and update root->data
        S.sum = S.sum + node.data;
        node.data = S.sum;
 
        // Recur for left subtree
        this.modifyBSTUtil(node.left, S);
    }
 
    // A wrapper over modifyBSTUtil()
    void modifyBST(Node node)
    {
        Sum S = new Sum();
        this.modifyBSTUtil(node, S);
    }
 
    // Driver Function
    public static void main(String[] args)
    {
        BinarySearchTree tree = new BinarySearchTree();
 
        /* Let us create following BST
              50
           /     \
          30      70
         /  \    /  \
       20   40  60   80 */
 
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);
 
        tree.modifyBST(tree.root);
 
        // print inorder traversal of the modified BST
        tree.inorder();
    }
}
 
// This code is contributed by Kamal Rawal

Python3

# Python3 program to add all greater values
# in every node of BST
 
# A utility function to create a
# new BST node
class newNode:
 
    # Constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Recursive function to add all greater
# values in every node
def modifyBSTUtil(root, Sum):
     
    # Base Case
    if root == None:
        return
 
    # Recur for right subtree
    modifyBSTUtil(root.right, Sum)
 
    # Now Sum[0] has sum of nodes in right
    # subtree, add root.data to sum and
    # update root.data
    Sum[0] = Sum[0] + root.data
    root.data = Sum[0]
 
    # Recur for left subtree
    modifyBSTUtil(root.left, Sum)
 
# A wrapper over modifyBSTUtil()
def modifyBST(root):
    Sum = [0]
    modifyBSTUtil(root, Sum)
 
# A utility function to do inorder
# traversal of BST
def inorder(root):
    if root != None:
        inorder(root.left)
        print(root.data, end =" ")
        inorder(root.right)
 
# A utility function to insert a new node
# with given data in BST
def insert(node, data):
     
    # If the tree is empty, return a new node
    if node == None:
        return newNode(data)
 
    # Otherwise, recur down the tree
    if data <= node.data:
        node.left = insert(node.left, data)
    else:
        node.right = insert(node.right, data)
 
    # return the (unchanged) node pointer
    return node
 
# Driver Code
if __name__ == '__main__':
     
    # Let us create following BST
    # 50
    #     /     \
    # 30     70
    #     / \ / \
    # 20 40 60 80
    root = None
    root = insert(root, 50)
    insert(root, 30)
    insert(root, 20)
    insert(root, 40)
    insert(root, 70)
    insert(root, 60)
    insert(root, 80)
 
    modifyBST(root)
 
    # print inorder traversal of the
    # modified BST
    inorder(root)
     
# This code is contributed by PranchalK

C#

using System;
 
// C# code to add all greater values to
// every node in a given BST
 
// A binary tree node
public class Node {
 
    public int data;
    public Node left, right;
 
    public Node(int d)
    {
        data = d;
        left = right = null;
    }
}
 
public class BinarySearchTree {
 
    // Root of BST
    public Node root;
 
    // Constructor
    public BinarySearchTree()
    {
        root = null;
    }
 
    // Inorder traversal of the tree
    public virtual void inorder()
    {
        inorderUtil(this.root);
    }
 
    // Utility function for inorder traversal of
    // the tree
    public virtual void inorderUtil(Node node)
    {
        if (node == null) {
            return;
        }
 
        inorderUtil(node.left);
        Console.Write(node.data + " ");
        inorderUtil(node.right);
    }
 
    // adding new node
    public virtual void insert(int data)
    {
        this.root = this.insertRec(this.root, data);
    }
 
    /* A utility function to insert a new node with 
    given data in BST */
    public virtual Node insertRec(Node node, int data)
    {
        /* If the tree is empty, return a new node */
        if (node == null) {
            this.root = new Node(data);
            return this.root;
        }
 
        /* Otherwise, recur down the tree */
        if (data <= node.data) {
            node.left = this.insertRec(node.left, data);
        }
        else {
            node.right = this.insertRec(node.right, data);
        }
        return node;
    }
 
    // This class initialises the value of sum to 0
    public class Sum {
        private readonly BinarySearchTree outerInstance;
 
        public Sum(BinarySearchTree outerInstance)
        {
            this.outerInstance = outerInstance;
        }
 
        public int sum = 0;
    }
 
    // Recursive function to add all greater values in
    // every node
    public virtual void modifyBSTUtil(Node node, Sum S)
    {
        // Base Case
        if (node == null) {
            return;
        }
 
        // Recur for right subtree
        this.modifyBSTUtil(node.right, S);
 
        // Now *sum has sum of nodes in right subtree, add
        // root->data to sum and update root->data
        S.sum = S.sum + node.data;
        node.data = S.sum;
 
        // Recur for left subtree
        this.modifyBSTUtil(node.left, S);
    }
 
    // A wrapper over modifyBSTUtil()
    public virtual void modifyBST(Node node)
    {
        Sum S = new Sum(this);
        this.modifyBSTUtil(node, S);
    }
 
    // Driver Function
    public static void Main(string[] args)
    {
        BinarySearchTree tree = new BinarySearchTree();
 
        /* Let us create following BST
              50
           /     \
          30      70
         /  \    /  \
       20   40  60   80 */
 
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);
 
        tree.modifyBST(tree.root);
 
        // print inorder traversal of the modified BST
        tree.inorder();
    }
}
 
// This code is contributed by Shrikant13

Javascript

<script>
 
// JavaScript code to add all greater values to
// every node in a given BST
 
// A binary tree node
class Node {
    constructor(val) {
        this.data = val;
        this.left = null;
        this.right = null;
    }
}
 
 
    // Root of BST
    var root = null;
 
 
    // Inorder traversal of the tree
    function inorder()
    {
        inorderUtil(this.root);
    }
 
    // Utility function for inorder traversal of
    // the tree
    function inorderUtil(node)
    {
        if (node == null)
            return;
 
        inorderUtil(node.left);
        document.write(node.data + " ");
        inorderUtil(node.right);
    }
 
    // adding new node
     function insert(data)
    {
        this.root = this.insertRec(this.root, data);
    }
 
    /* A utility function to insert a new node with
    given data in BST */
    function insertRec(node , data)
    {
        /* If the tree is empty, return a new node */
        if (node == null) {
            this.root = new Node(data);
            return this.root;
        }
 
        /* Otherwise, recur down the tree */
        if (data <= node.data) {
            node.left = this.insertRec(node.left, data);
        }
        else {
            node.right = this.insertRec(node.right, data);
        }
        return node;
    }
 
    // This class initialises the value of sum to 0
     class Sum {
     constructor(){
        this.sum = 0;
        }
    }
 
    // Recursive function to add
    // all greater values in
    // every node
    function modifyBSTUtil(node,  S)
    {
        // Base Case
        if (node == null)
            return;
 
        // Recur for right subtree
        this.modifyBSTUtil(node.right, S);
 
        // Now *sum has sum of nodes
        // in right subtree, add
        // root->data to sum and update root->data
        S.sum = S.sum + node.data;
        node.data = S.sum;
 
        // Recur for left subtree
        this.modifyBSTUtil(node.left, S);
    }
 
    // A wrapper over modifyBSTUtil()
    function modifyBST(node)
    {
        var S = new Sum();
        this.modifyBSTUtil(node, S);
    }
 
    // Driver Function
     
        /* Let us create following BST
              50
           /     \
          30      70
         /  \    /  \
       20   40  60   80 */
 
        insert(50);
        insert(30);
        insert(20);
        insert(40);
        insert(70);
        insert(60);
        insert(80);
 
        modifyBST(root);
 
        // print inorder traversal of the modified BST
        inorder();
 
// This code contributed by gauravrajput1
 
</script>

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *