Calculate running time and space for each method using big oh notation as a function of the number of nodes n in the BST

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

void

BSTMap::print() const {

printAux(root);

cout << endl;

}

// prints out a string representation of the whole BST using a reverse inorder traversal

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;

}

// INPUT: an integer key

// OUTPUT: if k is already in the ordered map, then output the node containing k

// otherwise, output the new node in the tree with the corresponding key k.

// POSTCONDITION: a node with key k exists in the BST

// if the BST was empty, then the new node becomes the root of the BST (and thus its only node)

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;

}

// 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);

}