Question

[C++] Find the Recurrence Relation equations for the following functions:

Please explain how you got these equations.

BSTClass::Node* BSTClass::createNode(const string x) {

   Node* newNode = new Node;

   newNode->data = x;
   newNode->left = nullptr;
   newNode->right = nullptr;

   return newNode;
}

void BSTClass::insertNode(const string x) {

   insertNodeUtil(x, root);
}

void BSTClass::insertNodeUtil(const string data, Node* subTreePtr) {

   if (root == nullptr) {
       root = createNode(data);
   }
   else if (data <= subTreePtr->data) {
       if (subTreePtr->left == nullptr) {
           subTreePtr->left = createNode(data);
       }
       else {
           insertNodeUtil(data, subTreePtr->left);
       }
   }
   else {
       if (subTreePtr->right == nullptr) {
           subTreePtr->right = createNode(data);
       }
       else {
           insertNodeUtil(data, subTreePtr->right);
       }

   }
}

void BSTClass::printInOrder() {

   printInOrderUtil(root);
   cout << endl;

}

void BSTClass::printInOrderUtil(Node* subTreePtr) {

   if (root == nullptr) {
       cout << "The TREE is Empty ..." << endl;
   }
   else {
       if (subTreePtr->left != nullptr) {
           printInOrderUtil(subTreePtr->left);
       }

       cout << subTreePtr->data << " ";

       if (subTreePtr->right != nullptr) {
           printInOrderUtil(subTreePtr->right);
       }
   }

}

bool BSTClass::findKey(const string key) {

   return findKeyUtil(key, root);
}

bool BSTClass::findKeyUtil(const string key, Node* subTreePtr) {

   if (root == nullptr) {
       cout << "Key (" << key << ") is NOT found, it is an empty tree ..." << endl;
       return false;
   }

   if (subTreePtr == nullptr) {
       cout << "Key (" << key << ") is NOT found" << endl;
       return false;
   }
   else if (subTreePtr->data == key) {
       cout << "Key (" << key << ") is FOUND" << endl;
       return true;
   }
   else if (key < subTreePtr->data) {
       return findKeyUtil(key, subTreePtr->left);
   }
   else {   
       return findKeyUtil(key, subTreePtr->right);
   }
}

int BSTClass::treeHeight() {

   if (root == nullptr)
       return 0;
   else
       return treeHeightUtil(root);

}

int BSTClass::treeHeightUtil(Node* subTreePtr) {

   if (subTreePtr == nullptr) {
       return 0;
   }
   else {
       int lHeight = treeHeightUtil(subTreePtr->left);
       int rHeight = treeHeightUtil(subTreePtr->right);

       return (lHeight >= rHeight ? lHeight + 1 : rHeight + 1);
   }
}

Answer 1

1.) BSTClass::Node* BSTClass::createNode(const string x).

This function will work in constant time, i.e., O(1).

2.) void BSTClass::insertNodeUtil(const string data, Node* subTreePtr)

This function is inserting the element either in the left part or right part of the tree or to the root. After we get the location, where we want to insert the element in the tree, it takes constant time to insert at that location.

So, the recurrence equation will be: T(n) = T(n/2) + Θ(1).

So the solution is Θ(Logn)

3.) void BSTClass::insertNode(const string x)

Since, this function is just calling the function insertNodeUtil(data, tree), the recurrence equation will be same.

i.e., T(n) = T(n/2) + Θ(1).

4.) void BSTClass::printInOrderUtil(Node* subTreePtr)

This function is first calling the left part of the tree and then the right part of the tree.

So, the recurrence equation will be: T(n) = 2*T(n/2) + Θ(1).

So the solution is Θ(n)

5.) Recurrence equation for function printInOrder() will be same as function printInOrderUtil().

6.) bool BSTClass::findKeyUtil(const string key, Node* subTreePtr)

This function will first compare the key to the root of the tree. Then, it will either go to the left part of tree or to the right part of the tree.

So, the recurrence equation will be: T(n) = T(n/2) + Θ(1).

So the solution is Θ(Logn)

7.) Recurrence equation for function findKey() will be same as function findKeyUtil().

8.)  int BSTClass::treeHeightUtil(Node* subTreePtr)

As the algorithm, visit each node of the tree exactly once.

This function is first calling the left part of the tree and then the right part of the tree.

So, the recurrence equation will be: T(n) = 2*T(n/2) + Θ(1).

So the solution is Θ(n)

9.) Recurrence equation for function treeHeight() will be same as function treeHeightUtil()