Use a recurrence tree to determine the best-, worst-, and average-case time

complexities of each public method of the CompleteTree class.

Use a recurrence relationship with the Master Method to determine the

best-, worst-, and average-case time complexities of each public method of the CompleteTree

class. Be sure to define all variables you use and show your work.

What is the total space complexity of each public method of the CompleteTree

class? For recursive functions, specify both the implicit and explicit space complexities.

2 Complete Trees #include #include #include algorithm #include using namespace std; void printArray (const vector int>k arr) { for (auto val : arr) { cout list) { vector nodes; // Create all the nodes, no left/right/parent set yet for (int value : list) { Node. n - new Node(); n->data = value; n->left = nullptr; n->right = nullptr: n->parent - nullptr: nodes. push_back(n); // Now loop through again and set the hierarchy based on the indezes of the array int nodeCount - nodes.size(): for (int i = 0; i left - nodes[leftChild(1)]: if (rightChild(1) right - nodes (right Child(1)]: Bodle root - nodes. empty() ? nullptr: nodes[0]; vector int> toArray() { vector int> arr; // Use a level order traversal to convert a complete tree // is hierarchical form to array form // Level order traversal is done using a Queue. queue levelOrder: levelOrder.push(root); while (!levelOrder.empty()) { Node* node = levelOrder.front(); levelOrder.pop(); if (node != nullptr) { arr.push_back(node->data); levelOrder.push(node->left); levelOrder.push(node->right); return arr; bool isBST() { // Use a helper that will check isBST at the given node. return isBST(root); void preOrder() { // Helper to do preOrder from a particular sode. preOrder (root); void post Order() { // Helper to do post Order from a particular node. postOrder (root); int numNodesInLookup (int value) { 1f (isBST) { return binarySearch(root, value, 0); // Not a binary search tree, so we need to do a linear search, // which can be done using a level order traversal. int nodesChecked = 0; queue Node> levelOrder; levelOrder.push(root); while (!levelOrder.empty()) { Node* node = levelOrder.front(); level Order.pop(); if (node != nullptr) { nodesChecked: if (node->data - value) { return nodesChecked; levelOrder.push(node->left); levelOrder.push(node->right); return -1: private: int binarySearch (Node node, int value, int nodesChecked) { // If node is nullptr then there are no nodes to check - return 0. if (node = nullptr) { return 0; // Otherwise, we are checking another mode, so increment nodesChecked nodesChecked++; it (node->data = value) { // We found it, return the count of nodesChecked. return nodesChecked; if (node->data > value) { return binarySearch(node->left, value, nodesChecked); return binarySearch(node->right, value, nodesChecked); bool isBST(Node. node) { vector int> data; inOrder (node, data); // If an in order traversal results in a sorted list, then it is a binary search tree. if (is_sorted(data.begin(), data.end()) { return true; return false; void preOrder (Node* node) { if (node -- nullptr) { return; : cout data left); preOrder (node->right); void post Order (Node* node) { if (node - nullptr) { return; post Order (node->left); postOrder (node->right); cout data if (node = nullptr) { return; in Order (node->left, d); d.push_back (node->data); inOrder (node->right, d); bool hasParent(int i) { return i > 0; int parent(int i) { return (1 - 1) / 2; int leftChild(int i) { return 2 i + 1; int rightChild(int i) { return 2.1 + 2; int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT / int numNodes; cin >> numNodes; vector int> values; for (int i = 0; i > value; values.push_back (value); CompleteTree t; t.from Array (values); int numCommands; cin >> numCommands; for (int i = 0; i > command; if (comnand "toArray") { printArray(t.toArray(); } else if (command - "isBST") { cout > value; cout #include #include algorithm #include using namespace std; void printArray (const vector int>k arr) { for (auto val : arr) { cout list) { vector nodes; // Create all the nodes, no left/right/parent set yet for (int value : list) { Node. n - new Node(); n->data = value; n->left = nullptr; n->right = nullptr: n->parent - nullptr: nodes. push_back(n); // Now loop through again and set the hierarchy based on the indezes of the array int nodeCount - nodes.size(): for (int i = 0; i left - nodes[leftChild(1)]: if (rightChild(1) right - nodes (right Child(1)]: Bodle root - nodes. empty() ? nullptr: nodes[0]; vector int> toArray() { vector int> arr; // Use a level order traversal to convert a complete tree // is hierarchical form to array form // Level order traversal is done using a Queue. queue levelOrder: levelOrder.push(root); while (!levelOrder.empty()) { Node* node = levelOrder.front(); levelOrder.pop(); if (node != nullptr) { arr.push_back(node->data); levelOrder.push(node->left); levelOrder.push(node->right); return arr; bool isBST() { // Use a helper that will check isBST at the given node. return isBST(root); void preOrder() { // Helper to do preOrder from a particular sode. preOrder (root); void post Order() { // Helper to do post Order from a particular node. postOrder (root); int numNodesInLookup (int value) { 1f (isBST) { return binarySearch(root, value, 0); // Not a binary search tree, so we need to do a linear search, // which can be done using a level order traversal. int nodesChecked = 0; queue Node> levelOrder; levelOrder.push(root); while (!levelOrder.empty()) { Node* node = levelOrder.front(); level Order.pop(); if (node != nullptr) { nodesChecked: if (node->data - value) { return nodesChecked; levelOrder.push(node->left); levelOrder.push(node->right); return -1: private: int binarySearch (Node node, int value, int nodesChecked) { // If node is nullptr then there are no nodes to check - return 0. if (node = nullptr) { return 0; // Otherwise, we are checking another mode, so increment nodesChecked nodesChecked++; it (node->data = value) { // We found it, return the count of nodesChecked. return nodesChecked; if (node->data > value) { return binarySearch(node->left, value, nodesChecked); return binarySearch(node->right, value, nodesChecked); bool isBST(Node. node) { vector int> data; inOrder (node, data); // If an in order traversal results in a sorted list, then it is a binary search tree. if (is_sorted(data.begin(), data.end()) { return true; return false; void preOrder (Node* node) { if (node -- nullptr) { return; : cout data left); preOrder (node->right); void post Order (Node* node) { if (node - nullptr) { return; post Order (node->left); postOrder (node->right); cout data if (node = nullptr) { return; in Order (node->left, d); d.push_back (node->data); inOrder (node->right, d); bool hasParent(int i) { return i > 0; int parent(int i) { return (1 - 1) / 2; int leftChild(int i) { return 2 i + 1; int rightChild(int i) { return 2.1 + 2; int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT / int numNodes; cin >> numNodes; vector int> values; for (int i = 0; i > value; values.push_back (value); CompleteTree t; t.from Array (values); int numCommands; cin >> numCommands; for (int i = 0; i > command; if (comnand "toArray") { printArray(t.toArray(); } else if (command - "isBST") { cout > value; cout