Recursive C++ alphabetical order function returning same value repeatedly

Question

Background: I am writing a program that takes a list of data and parses it into a binary search tree. The key for this data is of type "string". I'm working on writing a boolean function that returns "true" if the key of the data to be added precedes the key of the data in the reference node, "false" if the new key succeeds the old, and recursively runs back through the function, incrementing by one position, should the characters in question be equal is ASCII value.

Currently, it appears that my comparisons are correct and appears to be recursing correctly, but is returning false for all cases.

mBST.cpp

    class mBST {
    private:
        struct mNode {
            movie M;
            string k;
            mNode* left;
            mNode* right;
        };
        mNode *root;
        mNode *insert(movie m, mNode *t) {
            bool rec;
            if (t == NULL) {
                t = new mNode();
                t->M = m;
                t->k = m.getTitle();
                t->left = NULL;
                t->right = NULL;
            } else {
                if(abcOrder(m, t, 0)){
                    t->left = insert(m, t->left);
                }
                else {
                    t->right = insert(m, t->right);
                }
            }
            return t;
            };
            mNode *remove(movie m, mNode *t);
            mNode *search(string k, mNode *t);
            mNode *min(mNode *t);
            mNode *max(mNode *t);
            void inorder(mNode *t);


public:
    mBST() {
        root = NULL;
    }

    void insert(movie m) {
        root = insert(m, root);
    };
    void remove(movie m);
    void search(string k);
    void inorder();
    //Initial call passes i = 0
    bool abcOrder(movie m, mNode *ref, int i) {
        int data = NULL;
        //Gets key data and converts to lowercase as needed
        int newNode = m.getTitle().at(i);
        if (newNode < 97)
            newNode = newNode + 32;
        int refNode = ref->M.getTitle().at(i);
        if (refNode < 97)
            refNode = refNode + 32;
        //Compares key data at position 'i'
        if (newNode < refNode) {
            return true;
        } else if (newNode > refNode) {
            return false;
        } else {
            //If newNode.key == refNode.key, increment position and run again
            i++;
            abcOrder(m, ref, i);
        }
    }
};

MoviePeopleBST.cpp

int main()
{
ifstream inFile;
ofstream outFile;
mBST movieBST;
pBST peopleBST;

inFile.open("movies.txt");
//Reads in movies text file and sends to BST
while (!inFile.eof()) {
    string junk;
    string sTemp;
    movie temp;
    int iTemp;
    getline(inFile, sTemp);
    if (sTemp != "") {
        temp.setTitle(sTemp);
        inFile >> iTemp;
        temp.setYear(iTemp);
        getline(inFile, junk);
        inFile >> iTemp;
        temp.setRunTm(iTemp);
        getline(inFile, junk);
        getline(inFile, sTemp);
        temp.setRating(sTemp);
        getline(inFile, sTemp);
        temp.setAspect(sTemp);
        getline(inFile, sTemp);
        temp.setColor(sTemp);
        movieBST.insert(temp);
        //movieVector.push_back(temp);
    }
}
inFile.close();

/*inFile.open("people.txt");
//Reads in people text file and sends to BST
while (!inFile.eof()) {
    string junk;
    string sTemp;
    people temp;
    int iTemp;
    getline(inFile, sTemp);
    if (sTemp != "") {
        temp.setFirst(sTemp);
        getline(inFile, sTemp);
        temp.setLast(sTemp);
        inFile >> iTemp;
        temp.setbYear(iTemp);
        getline(inFile, junk);
        inFile >> iTemp;
        temp.setdYear(iTemp);
        getline(inFile, junk);
        getline(inFile, sTemp);
        temp.setGender(sTemp);
        peopleBST.insert(temp);
        //peopleVector.push_back(temp);
    }
}
inFile.close();*/

return 0;
}

Text File as data to insert:

laak
4
5
guide
payment
exclusive
laab
5
4
impartial
sigh
stage
laaj
9
8
change
cannon
wound
laal
8
7
acid
help
tickle

Given keys of: 1. laak 2. laab 3. laaj 4. laal

We should see an output of:

true (2 is left of 1)
true then false (3 is left of 1 and right of 2)
false (k is right of 1)

What it's actually returning is all false with 4 being the right child of 3, 3 being right of 2, and 2 being right of 1.

Note: Insertion method worked properly before I implemented this function, albeit with unique first characters.

Could you provide the entire code so that its possible to have a [Minimal, Complete, and Verifiable example](https://stackoverflow.com/help/mcve) — Vuwox, Apr 19 '19 at 02:26

score 1 · Accepted Answer · answered Apr 19 '19 at 02:42

1

return abcOrder(m, ref, i);

...

answered Apr 19 '19 at 02:42

Yakk - Adam Nevraumont

262,606
27
330
524

Can you please explain why this works and how it was even returning `false` without the `return`. – jackw11111 Apr 19 '19 at 02:50
1

https://stackoverflow.com/questions/1610030/why-does-flowing-off-the-end-of-a-non-void-function-without-returning-a-value-no – mangusta Apr 19 '19 at 03:02
Falling off the end of a function with a non-`void` return type gives undefined behaviour if the caller uses the returned value. The value received by the caller therefore can be anything. Returning `false` consistently is one perfectly valid outcome. But so is anything else. – Peter Apr 19 '19 at 03:32

Recursive C++ alphabetical order function returning same value repeatedly

1 Answers1