Suma de Nodes en un árbol de búsqueda binaria con valores de un rango dado

Dado un árbol de búsqueda binario que consta de N Nodes y dos números enteros positivos L y R , la tarea es encontrar la suma de los valores de todos los Nodes que se encuentran en el rango [L, R] .

Ejemplos:

Entrada: L = 7, R = 15
                    10
                   / \
                5 15
              / \ \
           3 7 18
Salida: 32
Explicación:
Los Nodes en el árbol dado que se encuentran en el rango [7, 15] son ​​{7, 10, 15}. Por tanto, la suma de los Nodes es 7 + 10 + 15 = 32.

Entrada: L = 11, R = 15
                     8
                   / \
                5 11
              / \ \
           3 6 20
Salida: 11

Enfoque: el problema dado se puede resolver realizando cualquier Tree Traversal y calculando la suma de los Nodes que se encuentran en el rango [L, R] .

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Class for node of the Tree
class Node {
public:
    int val;
    Node *left, *right;
};
 
// Function to create a new BST node
Node* newNode(int item)
{
    Node* temp = new Node();
    temp->val = item;
    temp->left = temp->right = NULL;
 
    // Return the newly created node
    return temp;
}
 
// Stores the sum of all nodes
// lying in the range [L, R]
int sum = 0;
 
// Function to perform level order
// traversal on the Tree and
// calculate the required sum
int rangeSumBST(Node* root, int low,
                int high)
{
    // Base Case
    if (root == NULL)
        return 0;
 
    // Stores the nodes while
    // performing level order traversal
    queue<Node*> q;
 
    // Push the root node
    // into the queue
    q.push(root);
 
    // Iterate until queue is empty
    while (q.empty() == false) {
 
        // Stores the front
        // node of the queue
        Node* curr = q.front();
        q.pop();
 
        // If the value of the node
        // lies in the given range
        if (curr->val >= low
            && curr->val <= high) {
 
            // Add it to sum
            sum += curr->val;
        }
 
        // If the left child is
        // not NULL and exceeds low
        if (curr->left != NULL
            && curr->val > low)
 
            // Insert into queue
            q.push(curr->left);
 
        // If the right child is not
        // NULL and exceeds low
        if (curr->right != NULL
            && curr->val < high)
 
            // Insert into queue
            q.push(curr->right);
    }
 
    // Return the resultant sum
    return sum;
}
 
// Function to insert a new node
// into the Binary Search Tree
Node* insert(Node* node, int data)
{
    // Base Case
    if (node == NULL)
        return newNode(data);
 
    // If the data is less than the
    // value of the current node
    if (data <= node->val)
 
        // Recur for left subtree
        node->left = insert(node->left,
                            data);
 
    // Otherwise
    else
 
        // Recur for the right subtree
        node->right = insert(node->right,
                             data);
 
    // Return the node
    return node;
}
 
// Driver Code
int main()
{
    /* Let us create following BST
         10   
        / \
       5   15
      / \     \
     3   7    18  */
    Node* root = NULL;
    root = insert(root, 10);
    insert(root, 5);
    insert(root, 15);
    insert(root, 3);
    insert(root, 7);
    insert(root, 18);
 
    int L = 7, R = 15;
    cout << rangeSumBST(root, L, R);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Class for node of the Tree
static class Node
{
    int val;
    Node left, right;
};
 
// Function to create a new BST node
static Node newNode(int item)
{
    Node temp = new Node();
    temp.val = item;
    temp.left = temp.right = null;
 
    // Return the newly created node
    return temp;
}
 
// Stores the sum of all nodes
// lying in the range [L, R]
static int sum = 0;
 
// Function to perform level order
// traversal on the Tree and
// calculate the required sum
static int rangeSumBST(Node root, int low,
                                  int high)
{
     
    // Base Case
    if (root == null)
    return 0;
 
    // Stores the nodes while
    // performing level order traversal
    Queue<Node> q = new LinkedList<Node>();
 
    // Push the root node
    // into the queue
    q.add(root);
 
    // Iterate until queue is empty
    while (q.isEmpty() == false)
    {
         
        // Stores the front
        // node of the queue
        Node curr = q.peek();
        q.remove();
 
        // If the value of the node
        // lies in the given range
        if (curr.val >= low &&
            curr.val <= high)
        {
             
            // Add it to sum
            sum += curr.val;
        }
 
        // If the left child is
        // not null and exceeds low
        if (curr.left != null &&
            curr.val > low)
 
            // Insert into queue
            q.add(curr.left);
 
        // If the right child is not
        // null and exceeds low
        if (curr.right != null &&
            curr.val < high)
 
            // Insert into queue
            q.add(curr.right);
    }
 
    // Return the resultant sum
    return sum;
}
 
// Function to insert a new node
// into the Binary Search Tree
static Node insert(Node node, int data)
{
     
    // Base Case
    if (node == null)
        return newNode(data);
 
    // If the data is less than the
    // value of the current node
    if (data <= node.val)
 
        // Recur for left subtree
        node.left = insert(node.left,
                           data);
 
    // Otherwise
    else
 
        // Recur for the right subtree
        node.right = insert(node.right,
                            data);
 
    // Return the node
    return node;
}
 
// Driver Code
public static void main(String[] args)
{
     
    /* Let us create following BST
         10   
        / \
       5   15
      / \     \
     3   7    18  */
    Node root = null;
    root = insert(root, 10);
    insert(root, 5);
    insert(root, 15);
    insert(root, 3);
    insert(root, 7);
    insert(root, 18);
 
    int L = 7, R = 15;
    System.out.print(rangeSumBST(root, L, R));
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program for the above approach
from collections import deque
 
# Class for node of the Tree
class Node:
    def __init__(self,v):
        self.val = v
        self.left = None
        self.right = None
 
# Function to perform level order
# traversal on the Tree and
# calculate the required sum
def rangeSumBST(root, low, high):
    sum = 0
     
    # Base Case
    if (root == None):
        return 0
 
    # Stores the nodes while
    # performing level order traversal
    q = deque()
     
    # Push the root node
    # into the queue
    q.append(root)
 
    # Iterate until queue is empty
    while (len(q) > 0):
 
        # Stores the front
        # node of the queue
        curr = q.popleft()
        # q.pop()
 
        # If the value of the node
        # lies in the given range
        if (curr.val >= low
            and curr.val <= high):
 
            # Add it to sum
            sum += curr.val
 
        # If the left child is
        # not NULL and exceeds low
        if (curr.left != None
            and curr.val > low):
 
            # Insert into queue
            q.append(curr.left)
 
        # If the right child is not
        # NULL and exceeds low
        if (curr.right != None
            and curr.val < high):
 
            # Insert into queue
            q.append(curr.right)
 
    # Return the resultant sum
    return sum
 
# Function to insert a new node
# into the Binary Search Tree
def insert(node, data):
   
    # Base Case
    if (node == None):
        return Node(data)
 
    # If the data is less than the
    # value of the current node
    if (data <= node.val):
 
        # Recur for left subtree
        node.left = insert(node.left, data)
    # Otherwise
    else:
        # Recur for the right subtree
        node.right = insert(node.right, data)
 
    # Return the node
    return node
 
# Driver Code
if __name__ == '__main__':
    # /* Let us create following BST
    #      10
    #     / \
    #    5   15
    #   / \     \
    #  3   7    18  */
    root = None
    root = insert(root, 10)
    root = insert(root, 5)
    root = insert(root, 15)
    root = insert(root, 3)
    root = insert(root, 7)
    root = insert(root, 18)
 
    L, R = 7, 15
    print(rangeSumBST(root, L, R))
 
# This code is contributed by mohit kumar 29.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Class for node of the Tree
class Node
{
    public int val;
    public Node left, right;
};
 
// Function to create a new BST node
static Node newNode(int item)
{
    Node temp = new Node();
    temp.val = item;
    temp.left = temp.right = null;
 
    // Return the newly created node
    return temp;
}
 
// Stores the sum of all nodes
// lying in the range [L, R]
static int sum = 0;
 
// Function to perform level order
// traversal on the Tree and
// calculate the required sum
static int rangeSumBST(Node root, int low,
                                  int high)
{
     
    // Base Case
    if (root == null)
    return 0;
 
    // Stores the nodes while
    // performing level order traversal
    Queue<Node> q = new Queue<Node>();
 
    // Push the root node
    // into the queue
    q.Enqueue(root);
 
    // Iterate until queue is empty
    while (q.Count!=0)
    {
         
        // Stores the front
        // node of the queue
        Node curr = q.Peek();
        q.Dequeue();
 
        // If the value of the node
        // lies in the given range
        if (curr.val >= low &&
            curr.val <= high)
        {
             
            // Add it to sum
            sum += curr.val;
        }
 
        // If the left child is
        // not null and exceeds low
        if (curr.left != null &&
            curr.val > low)
 
            // Insert into queue
            q.Enqueue(curr.left);
 
        // If the right child is not
        // null and exceeds low
        if (curr.right != null &&
            curr.val < high)
 
            // Insert into queue
            q.Enqueue(curr.right);
    }
 
    // Return the resultant sum
    return sum;
}
 
// Function to insert a new node
// into the Binary Search Tree
static Node insert(Node node, int data)
{
     
    // Base Case
    if (node == null)
        return newNode(data);
 
    // If the data is less than the
    // value of the current node
    if (data <= node.val)
 
        // Recur for left subtree
        node.left = insert(node.left,
                           data);
 
    // Otherwise
    else
 
        // Recur for the right subtree
        node.right = insert(node.right,
                            data);
 
    // Return the node
    return node;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    /* Let us create following BST
         10   
        / \
       5   15
      / \     \
     3   7    18  */
    Node root = null;
    root = insert(root, 10);
    insert(root, 5);
    insert(root, 15);
    insert(root, 3);
    insert(root, 7);
    insert(root, 18);
 
    int L = 7, R = 15;
    Console.Write(rangeSumBST(root, L, R));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript program for the above approach
 
// Class for node of the Tree
class Node
{
    // Function to create a new BST node
    constructor(item)
    {
        this.val=item;
        this.left=this.right=null;
    }
}
 
// Stores the sum of all nodes
// lying in the range [L, R]
let sum = 0;
 
// Function to perform level order
// traversal on the Tree and
// calculate the required sum
function rangeSumBST(root,low,high)
{
    // Base Case
    if (root == null)
        return 0;
  
    // Stores the nodes while
    // performing level order traversal
    let q = [];
  
    // Push the root node
    // into the queue
    q.push(root);
  
    // Iterate until queue is empty
    while (q.length!=0)
    {
          
        // Stores the front
        // node of the queue
        let curr = q.shift();
         
  
        // If the value of the node
        // lies in the given range
        if (curr.val >= low &&
            curr.val <= high)
        {
              
            // Add it to sum
            sum += curr.val;
        }
  
        // If the left child is
        // not null and exceeds low
        if (curr.left != null &&
            curr.val > low)
  
            // Insert into queue
            q.push(curr.left);
  
        // If the right child is not
        // null and exceeds low
        if (curr.right != null &&
            curr.val < high)
  
            // Insert into queue
            q.push(curr.right);
    }
  
    // Return the resultant sum
    return sum;
}
 
// Function to insert a new node
// into the Binary Search Tree
function  insert(node,data)
{
    // Base Case
    if (node == null)
        return new Node(data);
  
    // If the data is less than the
    // value of the current node
    if (data <= node.val)
  
        // Recur for left subtree
        node.left = insert(node.left,
                           data);
  
    // Otherwise
    else
  
        // Recur for the right subtree
        node.right = insert(node.right,
                            data);
  
    // Return the node
    return node;
}
 
// Driver Code
/* Let us create following BST
         10  
        / \
       5   15
      / \     \
     3   7    18  */
let root = null;
root = insert(root, 10);
insert(root, 5);
insert(root, 15);
insert(root, 3);
insert(root, 7);
insert(root, 18);
 
let L = 7, R = 15;
document.write(rangeSumBST(root, L, R));
 
     
 
// This code is contributed by patel2127
 
</script>
Producción

32

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Otro enfoque:
 en este enfoque, podemos aplicar directamente el recorrido en orden en el árbol de búsqueda binaria y si ese valor de Node se encuentra entre el rango [L, R], entonces simplemente podemos agregarlo a la suma.

C++

// C++ program for the above approach
// This Code is contributed by Omkar Subhash Ghongade
#include <bits/stdc++.h>
using namespace std;
 
// Class for node of the Tree
class Node {
public:
    int val;
    Node *left, *right;
};
 
// Function to create a new BST node
Node* newNode(int item)
{
    Node* temp = new Node();
    temp->val = item;
    temp->left = temp->right = NULL;
 
    // Return the newly created node
    return temp;
}
 
// Stores the sum of all nodes
// lying in the range [L, R]
int sum = 0;
 
// Function to perform level order
// traversal on the Tree and
// calculate the required sum
void rangeSumBST(Node* root, int low, int high, int* sum)
{
    if (root != NULL) {
        // Giving a call to the left subtree
        rangeSumBST(root->left, low, high, sum);
        // checking if the value at that node is in the
        // range or not.
        if (root->val >= low && root->val <= high)
            *sum += root->val;
        // Giving a call to the right subtree
        rangeSumBST(root->right, low, high, sum);
    }
}
 
// Function to insert a new node
// into the Binary Search Tree
Node* insert(Node* node, int data)
{
    // Base Case
    if (node == NULL)
        return newNode(data);
 
    // If the data is less than the
    // value of the current node
    if (data <= node->val)
 
        // Recur for left subtree
        node->left = insert(node->left, data);
 
    // Otherwise
    else
 
        // Recur for the right subtree
        node->right = insert(node->right, data);
 
    // Return the node
    return node;
}
 
// Driver Code
int main()
{
    /* Let us create following BST
            10
            / \
    5 15
    / \     \
    3 7 18 */
    Node* root = NULL;
    root = insert(root, 10);
    insert(root, 5);
    insert(root, 15);
    insert(root, 3);
    insert(root, 7);
    insert(root, 18);
 
    int L = 7, R = 15, sum = 0;
    rangeSumBST(root, L, R, &sum);
    cout << sum;
    return 0;
}
Producción

32

Complejidad de tiempo: O(n), n es el número de Nodes en el árbol.
Espacio Auxiliar: O(n), donde n es el número de Nodes en el árbol

Publicación traducida automáticamente

Artículo escrito por CoderSaty 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 *