Get Sum from Nodes Tree

find and return the sum of all nodes present in a generic tree in c++

For a generic tree with n children, you can think of the recurrence relation as:

sum(tree) = value(root) + sum(child[0]) + sum(child[1]) + ... + sum(child[n-1])

Then, the recursive solution is simply:

int sum(TreeNode<int>* root)
{
    // value(root)
    int s = root->data;

    // no. children
    int n = root->child.size();

    // + sum(child[0]) + sum(child[1]) + ... + sum(child[n-1])
    for (int i = 0; i < n; ++i) {
        s += sum(root->child[i]);
    }

    return s;
}

Get sum from nodes tree

LTREE

You are almost on the right track. You almost stumbled upon the 'LTREE' system of storing hierachial data in a database. You just need to make a slight modidification. that's all.

Your table might look like this:

CREATE TABLE Table1
    (`id` int, `parent_id` int, `name` varchar(13),
     `path` char(10),
     `money` int)
;

And your data might look like this.

(1, 0, 'company 1', '1', 10),
(2, 1, 'child 1', '1.1', 10),
(3, 2, 'child 2', '1.1.1', 10),
(4, 1, 'child 3', '1.2', 10,),
(4, 1, 'company 2', '2', 10),
(4, 1, 'child 2.1', '2.1', 10)

The path column helps to identify which company is a subsidiary of another company. Notice that you don't actually need to have an allmoney column. This is dynamically generated.

And how do you find all the money that belongs to the first company?

select sum(money) from Table1 where path >= '1' and path < '2'

Notice that in the structure that we have created, child1 is the parent for child2. So how do we find the allmoney for child1?

select sum(money) from Table1 where path >= '1.1' and path < '1.2'

There is only one query and no recursion.

MPTT

Another popular approach for fetching hierarchical data is using Modified Pre Order Tree Traversal. There has been an excellent article on Sitepoint for many years which explains how this is done with lot's of sample code.

How can I sum all nodes under a given value in binary search tree?

Ok, as this is an exercise, I won't fill everything, but I will try to give you an idea of how it should be done:

You need to create your tree, in a simple way you can do this:

def create_new_bst(lst):
    tree = BinarySearchTree(tree[0])
    # And then, using the insert method, which is correct, add your nodes in the tree
    return tree

First, you need to find Your subtree with the root 72

# Replace the pass with the appropriate code

def find_subtree(tree, value):
    if value == tree.data: # This is found yeah !
         pass
    if value > tree.data: # Ok, this is not our data, we should look recursively in one of the children (I will not tell you which one). Maybe we can use find_subtree reccursively?
         pass
    if value < tree.data: # Same as above, but maybe we should look in the other child
         pass
    raise ValueError("Not found value " + str(value)) # Nothing has been found.

Now, you found the tree with my_tree = find_subtree(t, 72), you should just sum the left tree (if it exists) and the right tree (if it exists)

def sum_beneath(t, value):
    my_tree = find_subtree(t, value)
    s = 0
    if my_tree.left is not None:
         s += my_tree.left.sum_tree()
    if my_tree.right is not None:
         s += my_tree.right.sum_tree()
    return s

Let's define the sum_tree method (in the class)! :)

def sum_tree(self):
    ans =  self.data
    # Add the left sum reccursively
    # Add the right sum reccursively
    return ans

I hope this will help you to understand the concept of BST. If you need help do not hesitate to comment

How to calculate the sum of the children in a general tree using Javascript

The logic can be simplified by recursively calculating the children's sum first, and then returning the sum of the children values and the parents value.

const tree = {  name: "Root Node",  value: 0,  sumOfTheChildren: 0,  children: [{
      name: "A Node",      value: 10,      sumOfTheChildren: 0,      children: [{
        name: "D Node",        value: 35,        sumOfTheChildren: 0,        children: []      }]    },
    {
      name: "B Node",      value: 10,      sumOfTheChildren: 0,      children: []    }
  ]};
function postOrder(root) {  if (root.children) {    root.children.forEach(child => {      root.sumOfTheChildren += postOrder(child);    });  }
  return root.sumOfTheChildren + root.value;}
console.log(postOrder(tree));console.log(tree);

How to sum left nodes from binary tree javascript

function leftmostNodesSum(array) {
  let sum = 0;
  let currentNode = 0;
  for (let i = 0; i < array.length; i++) {        
    if (i === currentNode) {          
      sum += array[i];
      currentNode = 2 * i + 1;
    }
    
  }
  return sum;
}

Sum of last N nodes in a binary search tree

You can simply visit the tree in reverse order, that means starting from root and do three things:

1. visit right branch
2. visit self node, and accumulate sum if needed
3. visit left branch

And stop iterating when k items are accumulated.

#include    <iostream>

struct Node {
    int value;
    Node* left = nullptr;
    Node* right = nullptr;
    Node(int v) : value(v) {}
};

// Visit the tree in reverse order and get sum of top k items.
int sumK(Node* root, int& k) {
    if (root == nullptr) return 0;
    int sum = 0;
    if (k > 0 && root->right) {
        sum += sumK(root->right, k);
    }
    if (k > 0) {
        sum += root->value;
        k--;
    }
    if (k > 0 && root->left) {
        sum += sumK(root->left, k);
    }
    return sum;
}

int main () {
    // The following code hard coded a tree matches the picture in your question.
    // I did not free the tree, so there will be memory leaking, but that is not relevant to this test.
    Node* root = new Node(5);
    root->right = new Node(6);
    root->right->right = new Node(7);
    root->left = new Node(3);
    root->left->right = new Node(4);
    root->left->left = new Node(2);
    root->left->left->left = new Node(1);
    // TODO: delete the tree after testing.

    int k = 1;
    std::cout << "k=" << k << " sum=" << sumK(root, k) << std::endl;
    k = 3;
    std::cout << "k=" << k << " sum=" << sumK(root, k) << std::endl;
    k = 4;
    std::cout << "k=" << k << " sum=" << sumK(root, k) << std::endl;
}

The output is:

k=1 sum=7
k=3 sum=18
k=4 sum=22

Sum of all children nodes values in a specific range

The problem is that you only visit child nodes that are within your range. This means if node2 has value 2 its children are never visited and you cannot sum the values 3 and 4. The solution to your problem is removing the if condition in the loop like this:

    public int sumRange(Node root, int min, int max) {
        int sum = 0;

        if(root.data >= min && root.data <= max) {
            sum = root.data;
        }

        int size = root.children.size();
        for (int i = 0; i < size; ++i) {
                sum += sumRange(root.children.get(i), min, max);
        }
        
        return sum;
    }

If you try again the output should be 12 for node 1.

---

Related Topics