uses g++ to compile C++

Finish the function Calculates the sum

Calculates the sum of all keys in every subtree in the BST, starting from the root

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

// Utility functions

void loadFile(string fname, fstream& file)

{

file.open(fname.c_str());

if (file.fail())

{

cout << "Cannot open file " << fname << endl;

}

}

// converts string to lowercase

string lowercase(string s)

{

for (unsigned int i = 0; i < s.length(); i++)

{

s[i] = std::tolower(s[i]);

}

return s;

}

class BSTMap

{

public:

struct Node {

int key;

int ht;

int sum;

Node* left;

Node* right;

Node* parent;

Node(int k, int s) :

key(k), sum(s), left(NULL), right(NULL), parent(NULL) { }

Node(int k, int s, Node* l, Node* r, Node* p) :

key(k), sum(s), left(l), right(r), parent(p) { }

};

public:

typedef BSTMap::Node Node;

public:

Node* root;

private:

int n;

protected:

void printAux(const Node* w) const; // print utility

public:

BSTMap() : root(NULL), n(0) { };

Node** find(int k) const;

Node* put(int k);

void calcSum(Node* s);

int size() const;

bool empty() const;

void print() const; // print as parenthetic string

void printTree(Node* s, int space) const;

};

void

BSTMap::printAux(const Node* w) const {

if (w) {

cout << "[" << w->key << ":" << w->sum << "]";

cout << "(";

printAux(w->left);

cout << "),(";

printAux(w->right);

cout << ")";

}

}

// print out a parenthetic string representation of the whole BST

void

BSTMap::print() const {

printAux(root);

cout << endl;

}

void

BSTMap::printTree(Node* s, int space) const {

int addSpace = 8;

// base case

if (!s)

{

return;

}

// add more whitespace

space = space + addSpace;

// print right

this->printTree(s->right, space);

cout << endl;

for (int i = addSpace; i < space; i++)

cout << " ";

cout << s->key << ":" << s->sum << endl;

// print left

this->printTree(s->left, space);

}

// INPUT: a key k, as an integer

// OUTPUT: a 2-element array, where

// element 0 is w, the node with key k, if k is already in the ordered map, or NULL

otherwise; and

// element 1 is z, the parent of node w, or NULL if w is NULL or the root

// or the last node visited while trying to find a node with key k in the BST

BSTMap::Node**

BSTMap::find(int k) const {

Node* w = root;

Node* z = NULL;

while (w && (w->key != k)) {

z = w;

w = (w->key > k) ? w->left : w->right;

}

Node** wAndZ = new Node*[2];

wAndZ[0] = w;

wAndZ[1] = z;

return wAndZ;

}

BSTMap::Node*

BSTMap::put(int k) {

Node** wAndZ = find(k);

Node* w = wAndZ[0];

Node* z = wAndZ[1];

delete wAndZ;

if (w) {

return w;

}

Node* x = new Node(k,0,NULL, NULL,z);

if (z) {

if (z->key > k) z->left = x;

else z->right = x;

}

else root = x;

n++;

if (n == 1) root = x;

return x;

}

// INPUT: a pointer to a Node in the tree s

// PRECONDITION:

// POSTCONDITION:

void

BSTMap::calcSum(Node* s) {

// Your code here

}

// OUTPUT: size of the tree

int

BSTMap::size() const {

return n;

}

// OUTPUT: true if the tree is empty; false otherwise

bool

BSTMap::empty() const {

return (!root);

}

int main() {

string inputFilename = "input.txt";

string line;

BSTMap B;

// open input file

fstream inputFile;

loadFile(inputFilename, inputFile);

while (getline(inputFile, line))

{

// trim whitespace

// echo input

cout << line << endl;

// parse input using a stringstream

stringstream lineSS(line);

string token;

string command;

// store tokens in a vector

vector tokens;

while (getline(lineSS, token, ' '))

{

// trim whitespace

token.erase(token.find_last_not_of(" \t") + 1);

tokens.push_back(token);

}

if (tokens.size() > 0)

{

command = tokens[0]; // first token is the command

}

else

{

command = "";

}

if (command == "put")

{

// insert a node for each key specified

for (unsigned int i = 1; i < tokens.size(); i++)

{

B.put(stoi(tokens[i]));

}

}

if (command == "sum")

{

B.calcSum(B.root);

}

if (command == "print")

{

B.print();

}

if (command == "printTree")

{

B.printTree(B.root, 0);

}

}

inputFile.close();

return EXIT_SUCCESS;

}