C++: Sum of all node values of a binary tree

Question

I'm preparing for a job interview. I was stuck at one of the binary tree questions:

How can we calculate the sum of the values present in all the nodes of a binary tree?

Thanks in advance.

Answer 1

The same way you search the tree, or display each node, or any other tree-wide operation: visit the current node, visit the left sub-tree (recursively), and visit the right sub-tree (recursively).

Essentially, something like this:

int TreeNode::calculateSum() const
{
    int sum = this->value;

    if (this->left  != NULL) sum += this->left ->calculateSum();
    if (this->right != NULL) sum += this->right->calculateSum();

    return sum;
}

Because of the if checks the recursion will eventually bottom out when it reaches nodes with no left or right children (leaf nodes).

Answer 2

While the STL has more complex and concise mechanisms for doing this, it's a very fast rode to productivity just to learn to use a manual loop over a container, something like:

Tree::value_type total = Tree::value_type();
for (Tree::const_iterator i = tree.begin(); i != tree.end(); ++i)
    total += *i;

This assumes your binary tree is a STL::map, or if not you'll provide an iterator concept for your own implementation....

Answer 3

Use one of the Tree Traversal techniques(In-order, Pre-order, Post-order) to visit each node and store the sum in a variable.

You can find more details on tree traversal in this wiki

Answer 4

The elegant recursive solution (in pseudo-code):

def sum (node):
    if node == NULL:
        return 0
    return node->value + sum (node->left) + sum (node->right)

then just use:

total = sum (root)

This correctly handle the case of a NULL root node.

---

And if you want to see it in action in C++, here's some code following the same algorithm:

#include <iostream>

typedef struct sNode {
    int value;
    struct sNode *left;
    struct sNode *right;
} tNode;

static int sum (tNode *node) {
    if (node == 0)
        return 0;
    return node->value + sum (node->left) + sum (node->right);
}

 

static void addNode (tNode *parent, char leftRight, int value) {
    tNode *node = new tNode();
    node->value = value;
    node->left = 0;
    node->right = 0;
    if (parent == 0)
        return;
    if (leftRight == 'L')
        parent->left = node;
    else
        parent->right = node;
}

int main (void) {
    tNode *root = 0;
    std::cout << sum (root) << std::endl;

    root = new tNode();
    root->value = 10;
    root->left = 0;
    root->right = 0;
    addNode (root,'L',7);
    addNode (root,'R',20);
    addNode (root->left,'L',3);
    addNode (root->left->left,'R',4);
    addNode (root->left->left->right,'R',6);
    addNode (root->right,'R',99);
    std::cout << sum (root) << std::endl;

    return 0;
}

which outputs (the correct):

0
149

Answer 5

Traverse the tree in any order (pre, post, in). Instead of printing the node calculate the total.

void sum(Node* root, int& total)
{
if(root == NULL) { return; }
sum(root->left, total);
total = total + root->value;
sum(root->right, total);
}
int main()
{
int total =0;
sum(root,total);
cout << total;
}