Calculating the sum of each level in the tree

Question:

Given a binary tree with nodes containing integer values. Your algorithm should calculate the sum of values in each depth and returns sums.

Example:

          1
         /   \
       2     3
      /  \   /  \
    4   5 1    2

Output:  1, 5, 12

Answer

I don't remember where I saw this problem. If I remember I will update the labels.

I am still struggling with editing my layout. I would like to show the labels rather than the archive.
If you know how to do it, please, leave a comment. It will be a true win-win.

As the title indicates, it is a classic breast first search(BFS) problem. Using the BFS you can sum up the values and store in the output to return at the end of the problem.

Time complexity : $(N)$
Space complexity:  $O(N)$

Here is the C++ source

	#include<iostream>
	#include<list>
	using namespace std;
	struct node {
	int value;
	node *left;
	node *right;
	node(int v):value(v), left(0), right(0){}
	};
	list<int> addup(node* r)
	{
	list<int> result;
	list<node*> queue;
	int cur_level= 0;
	int next_level = 0;
	int total = 0;
	if (!r)
	return result;
	queue.push_back(r);
	cur_level++;
	while(queue.size())
	{
	node *cur = queue.front();
	queue.pop_front();
	if (cur->left)
	{
	queue.push_back(cur->left);
	next_level++;
	}
	if (cur->right)
	{
	queue.push_back(cur->right);
	next_level++;
	}
	cur_level--;
	total += cur->value;
	if (cur_level==0)
	{
	result.push_back(total);
	cur_level = next_level;
	next_level = 0;
	total = 0;
	}
	}
	return result;
	}
	int main()
	{
	node * n1 = new node(1);
	node * n2 = new node(2);
	node * n3 = new node(3);
	node * n4 = new node(4);
	node * n5 = new node(5);
	node * n11 = new node(1);
	node * n22 = new node(2);
	n1->left = n2;
	n1->right = n3;
	n2->left = n4;
	n2->right = n5;
	n3->left = n11;
	n3->right = n22;
	list<int> result = addup(n1);
	list<int>::iterator iter;
	for (iter = result.begin(); iter!=result.end(); iter++)
	cout<<(*iter)<<", ";
	cout<<endl;
	return 1;
	}

view raw bfs1.cpp hosted with ❤ by GitHub

UPDATE(2019-07-31): Solved the problem in python. I wrote the code quickly but got the test cases wrong. Took too long to find that bug after adding two print statements.

	from collections import deque
	class Node:
	def __init__(self, value):
	self.value = value
	self.left = self.right = None
	def calculate_bfs(root):
	queue = deque()
	queue.append(root)
	current_children = 1
	next_children = 0
	current_level_sum = 0
	result = []
	while len(queue) > 0:
	current = queue.popleft()
	current_children -= 1
	current_level_sum += current.value
	if current.left != None:
	queue.append(current.left)
	next_children += 1
	if current.right != None:
	queue.append(current.right)
	next_children += 1
	if current_children == 0:
	result.append(current_level_sum)
	current_children = next_children
	next_children = 0
	current_level_sum = 0
	return result
	#test code
	n1 = Node(1)
	n2 = Node(2)
	n3 = Node(3)
	n4 = Node(4)
	n5 = Node(5)
	n6 = Node(6)
	n7 = Node(7)
	n1.left = n2
	n1.right = n3
	n2.left = n4
	n2.right = n5
	n3.left = n6
	n3.right = n7 # bug
	print ("root = {} sums = {}".format(n1.value, calculate_bfs(n1)))

view raw linkedin_sum_up_in_same_depth_bfs.py hosted with ❤ by GitHub

Practice statistics

7:00: to come up with an algorithm
13:00: to write up the code and test code (no bug)
07:00: to find the bug in the test code. (building the tree was wrong).

Total: 26:20

UPDATE(2022-06-14): solved again with no errors. Used python list as a queue.

	# code
	class Node:
	def __init__(self, value):
	self.value = value
	self.left = None
	self.right = None
	def calculate_level_sums(root):
	result = []
	queue = []
	sum = 0
	next = 0
	queue.append(root)
	cur = 1
	while len(queue) > 0:
	node = queue.pop(0)
	sum = sum + node.value
	cur = cur - 1
	if node.left != None:
	queue.append(node.left)
	next = next + 1
	if node.right != None:
	queue.append(node.right)
	next = next + 1
	if cur == 0: # end of current level
	result.append(sum)
	cur = next
	sum = 0
	next = 0
	return result
	# test
	c1 = Node(1)
	c2 = Node(2)
	c3 = Node(3)
	c1.left = c2
	c1.right = c3
	c4 = Node(4)
	c5 = Node(5)
	c2.left = c4
	c2.right = c5
	c6 = Node(1)
	c7 = Node(2)
	c3.left = c6
	c3.right = c7
	result = calculate_level_sums(c1)
	print ("level sums = {}".format(result))

view raw calculate_level_sums.py hosted with ❤ by GitHub

04:32: for algorithm and pseudo code

08:18: to write up the code