Adam Adam - 1 month ago 8
C++ Question

How to make this function non-recursive?

Hello it was suggested to me that I learn to write things non-recursively to understand what is going on much more clearly in the program. It is a binary search program that reads a .dat file of a list of presidents and sorts them alphabetically. Here is my code that I want to make non-recursive:

BstNode* Insert(BstNode* root, string data) {

if (root == NULL) {
root = GetNewNode(data);
}
else if (data <= root->data) {
root->left = Insert(root->left, data);
}
else {
root->right = Insert(root->right, data);
}
return root;

}


I want to understand what recursion is and how to look at something recursive and make it non recursive. I'm having trouble understanding these concepts. I'm not sure if I would need to adjust the rest of the binary search tree if I made that portion non-recursive.

Here's the full program in case you need to see what else is going on:

#include <stdio.h>
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

struct BstNode {

string data;
BstNode* left;
BstNode* right;

};

BstNode* GetNewNode(string data) {

BstNode* newNode = new BstNode();
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;

}



BstNode* Insert(BstNode* root, string data) {

if (root == NULL) {
root = GetNewNode(data);
}
else if (data <= root->data) {
root->left = Insert(root->left, data);
}
else {
root->right = Insert(root->right, data);
}
return root;

}

bool Search(BstNode* root, string data) {

if (root == NULL) return false;
else if (root->data == data) return true;
else if (data <= root->data) return Search(root->left, data);
else return Search(root->right, data);

}

void Print(BstNode*x) {

if (!x) return;
Print(x->left);
cout << ' ' << x->data << endl;
Print(x->right);
}

int main() {

BstNode* root = NULL; //creating an empty tree
//root = Insert(root, "adam"); test
//root = Insert(root, "greg"); test
//root = Insert(root, "tom"); test
//root = Insert(root, "bill"); test
//root = Insert(root, "sarah"); test
//root = Insert(root, "john"); test

ifstream fin;
fin.open("prez.dat");
string currentprez;
string input = "";

while (!fin.eof()) {

fin >> currentprez;
root = Insert(root, currentprez);
}

for (;;) {
string input = "";
cout << "Would you like to 'search', 'insert', 'print' or 'quit'?\n";
cin >> input;

//if user searches
if (input == "search" || input == "Search") {

string searchstr = "";
cout << "Enter string to be searched: \n";
cin >> searchstr;
if (Search(root, searchstr) == true) cout << searchstr + " was Found\n";
else cout << "Not Found\n";

}
//if user inserts
else if (input == "insert" || input == "Insert") {

string insertstr = "";
cout << "Enter string to be inputted: \n";
cin >> insertstr;
if (Search(root, insertstr) == true) cout << insertstr + " already exists\n";
else root = Insert(root, insertstr);

}

//if user prints
else if (input == "print" || input == "Print") Print(root);
//if user quits
else if (input == "quit" || input == "Quit") return(0);
//if anything else
else cout << "Invalid input\n";


}


}

Answer

Tree algorithms like this are actually very well suited for recursion, but a way to do it without recursion could be this:

BstNode* Insert(BstNode* root, string data) {
    if (root == null) {
        return GetNewNode(data);
    }    

    BstNode* prev = null;
    BstNode* pos = root;
    while (pos != null) {
        prev = pos;
        if (data <= pos->data) {
            pos = pos->left;
        }
        else {
            pos = pos->right;
        }
   }
   if ( data <= prev -> data) {
       prev -> left = GetNewNode(data);
   }else {
       prev -> right = GetNewNode(data);
   }

   return root;
}