[to understand the context of this problem, you should read the class #07 exercise sheet]

[AED044] Sum of All Levels

In this problem you should only submit a binaryTree.h file with a self-containing definition of a class BTree<T>

Base Code

Use as a basis the class BTree<T> (see code | download code) which implements a generic binary tree that was explained in classes, with methods to read a tree from standard input, to write several node traversals, to count the number of nodes, to compute the height and to see if it contains a certain value.

The Problem

Add a new method std::vector<int> sumLevels() const to the class. The method does not change the tree, so it should be const (as seen in the lectures). The function should return a vector containing the sum of the nodes of each level. The vector should have size equal to the number of levels and the sums should come from the first to the last level. The method will only be called with a tree of integer nodes.

The following figure illustrates a binary tree. For this tree the return vector should be {6,13,40,17}.

Submission

You should submit the file binaryTree.h with the method sumLevels added to binaryTree<T> as requested (and without removing any of the other existing methods). You can however create additional methods, if you need them.

Mooshak will use the following code to link to your class, read the inputs, build the trees and call your method, printing its result.

#include <iostream>
#include <string>
#include <vector>

#include "binaryTree.h"

// Read a tree of ints assuming "N" as the null value
// call t.sumLevels() method and write its output
void read() {
  BTree<int> t;
  t.read("N");

  std::cout << "t.sumLevels() = {";
  std::vector<int> sum = t.sumLevels();
  for (int i=0; i<(int)sum.size(); i++) {
    if (i>0) std::cout << ",";
    std::cout << sum[i];
  }
  std::cout << "}" << std::endl;
}

int main() {

  int n;
  std::cin >> n;
  for (int i=0; i<n; i++) read();
  
  return 0;
}

3
6 3 2 N 1 N N 5 N 7 N N 10 8 N 9 N N 25 N N
1 2 3 4 5 6 N N N N N N N
14 4 3 N N 9 7 5 N N N N 18 16 15 N N 17 N N 20 N N

t.sumLevels() = {6,13,40,17}
t.sumLevels() = {1,2,3,4,5,6}
t.sumLevels() = {14,22,48,39,5}

The first tree of the example input corresponds to the figure given above.