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?
Add a comment
|
7 Answers
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 handles the case of a NULL root node.
And if you want to see it in action in C++, here's some code using that algorithm. First, the structure for a node and the sum function:
#include <iostream>
typedef struct sNode {
int value;
struct sNode *left;
struct sNode *right;
} tNode;
int sum (tNode *node) {
if (node == 0) return 0;
return node->value + sum (node->left) + sum (node->right);
}
Then the code below is a test harness code for inserting nodes:
static tNode *addNode (tNode *parent, char leftRight, int value) {
tNode *node = new tNode();
node->value = value;
node->left = 0;
node->right = 0;
if (parent != 0) {
if (leftRight == 'L') {
parent->left = node;
} else {
parent->right = node;
}
}
return node;
}
And, finally, the main function for constructing the following tree, one that covers all of the valid possibilities (empty node, node with two children, node with no children, node with one right child and node with one left child):
10
/ \
7 20
/ \
3 99
\
4
\
6
The code to construct that tree and report the sum at various points is shown here:
int main (void) {
// Empty tree first.
tNode *root = 0;
std::cout << sum (root) << '\n';
// Then a tree with single node (10).
root = addNode (0, ' ', 10);
std::cout << sum (root) << '\n';
// Then one with two subnodes (10, 7, 20).
addNode (root,'L',7);
addNode (root,'R',20);
std::cout << sum (root) << '\n';
// Then, finally, the full tree as per above.
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) << '\n';
return 0;
}
This outputs (the correct):
0
10
37
149
4 Comments
Manoj R
shouldn't the last line be return sum(node->left) + sum(node->right) + node->val;
paxdiablo
Yes, caught me mid-edit. I had just been wondering where the value of the current node was coming from... Fixed now :-)
csguy11
Thanks a lot Paxdiablo. Btw, this is an O(n) algorithm right? Since it visits each of the n nodes only once.
paxdiablo
Yes, it is O(n). I had to think about that since binary trees are normally O(log n) but that's for a search, not retrieval. Traversing every node is indeed O(n).
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;
}
Comments
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).
Comments
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....
5 Comments
Eli Bendersky
I wouldn't give this as an answer to said interview question
Potatoswatter
I wish this were my first thought. +1. A tree in C++ may be just another sequence.
Tony Delroy
@Eli: the impression depends on phrasing. Asked "sum the nodes in a binary tree", saying "in C++ the STL's std::map<> is the Standard's binary tree; using its public interface a simple, general way to sum nodes is XXX. It's equally applicable to other iterator-sporting abstractions." then I think that would be a sound answer. Knowing people think first at the STL level (or higher Design Pattern level where applicable) is reassuring. At worst, the interviewer may prompt more explicitly for the recursive approach outlined in other answers to this question, or want to compare the two.
Eli Bendersky
Showing a good knowledge of C++/STL isn't showing a good knowledge of algorithms and data structures, and I'm willing to bet that it's the latter to which such an interview question refers.
Tony Delroy
Put another way, you're being asked for an algorithm... why not make it generic as indeed the STL tends to? Having someone demonstrate that they know the std::map<> is a tree is already a big step in the right direction. Anyway... I've presented the possibility - up to each reader here to decide if they'd like to use it at interview and how, or what they'd make of a candidate doing so.
50 / \ 30 70 / \ / \ 20 40 60 80returns:350
int Sum(struct node *root)
{
if(root->left == NULL && root->right== NULL)
return root->key;
int lvalue,rvalue;
lvalue=Sum(root->left);
rvalue=Sum(root->right);
return root->key+lvalue+rvalue;
}
Comments
public int sum(Node root){
if(root==null){
return 0;
}
if(root.left == null && root.right==null){
return root.key;
}
return sum(root.left)+sum(root.right)+root.key;
}
1 Comment
AdrianHHH
Answering questions is good but this question already has answers with very similar code. Any new answer should add different methods or add a better explanation of why the method is good. A code only answer, like this one, that just repeats what has already been provided adds nothing useful.