Binary Search Tree: root remains null during Inorder (C++)

Question

So I'm a little new to Binary search trees and I'm trying to make a binary tree where each node is a vector of strings. then each insertion takes a string and only considers the first letters of that string. Based off the first 2 letters it will either append that string to an existing node where all string share the same 2 first letters or create a new node which will hold a vector of strings with all the same 2 first letters. Weird I know. It wasn't my idea.

I've tried narrowing down where the issue is by displaying the root at every insertion. And the insertions all seem to be working fine, but as soon as I want to display the nodes in Inorder, the root just seems to disappear, BUT almost like it's invisible. It's very evident base on the output. My guess is that it's null but I'm not sure. Sorry if this isn't the best way to ask. this is my first question here.

here's my code:

#include <iostream> 
#include <string>
#include <vector>
//#include "stringSlicer.h"
using namespace std; 
  
class BST  
{ 
    vector<string> data; 
    BST *left, *right; 
  
public: 
    // Default constructor. 
    BST(); 
  
    // Parameterized constructor. 
    BST(string); 
  
    // Insert function. 
    BST* Insert(BST*, string); 
  
    // Inorder traversal. 
    void Inorder(BST*); 

    // PreOrder Traversal.
    void PreOrder(BST*);

    // PostOrder Traversal
    void PostOrder(BST*);

    // string slicer
    string strSlice(string);

    // print vector
    void printVector(vector<string>);
}; 
  
// Default Constructor definition. 
BST ::BST() 
    : data(0) 
    , left(NULL) 
    , right(NULL) 
{ 
} 
  
// Parameterized Constructor definition. 
BST ::BST(string value) 
{ 
    if(data.empty()){
        data.push_back(strSlice(value));
    }
        data.push_back(value); 
    
    left = right = NULL; 
} 
  
// String slicing function definition
string BST ::strSlice(string word){
    string word2 = "";
    word2 += word[0];
    word2 += word[1];
    return word2;
}


// print vector function definition
void BST ::printVector(vector<string> dataVector){
    for(int i = 0; i < dataVector.size(); i ++){
        cout << dataVector.at(i) << " ";
        cout << "end of this node";
    }
}

// Insert function definition. 
BST* BST ::Insert(BST* root, string value) 
{ 
    if (!root)  
    { 
        // Insert the first node, if root is NULL. 

        return new BST(value); 
    } 
  
    // Insert data. 
    if (strSlice(value).compare(root->data.at(0)) > 0)  
    { 
        // Insert right node data, if the 'value' 
        // to be inserted is greater than 'root' node data. 
        cout << value << " is being put in the right node " << value << " > " << root->data.at(0) << endl;
        // Process right nodes. 
        root->right = Insert(root->right, value); 
        
    } else if (strSlice(value).compare(root->data.at(0)) == 0) {

        cout << value << " is being put in the same node " << value << " = " << root->data.at(0)  << endl;
        root->data.push_back(value);
    }
    else 
    { 
        // Insert left node data, if the 'value' 
        // to be inserted is greater than 'root' node data. 
        cout << value << " is being put in the left node " << value << " < " << root->data.at(0) << endl;
        // Process left nodes. 
        root->left = Insert(root->left, value); 
    } 
  
    // Return 'root' node, after insertion. 
    cout << "after insert root is " << root << endl;
    return root; 
} 
  
// Inorder traversal function. 
// This gives data in sorted order. 
void BST ::Inorder(BST* root) 
{ 
    cout << "root is " << endl;
    if (!root) { 
        return; 
    } 
    Inorder(root->left); 
    printVector(data);
    cout << endl; 
    Inorder(root->right); 
} 

int main() {
    const int size = 5;
    string array [size] = {"hi","hillo","bye","chao","elo"};


     BST b, *root = NULL;
     cout << "root is " << root << endl;
     root = b.Insert(root, array[0]); 
     for (int i = 1; i < size; i ++){
         b.Insert(root, array[i]);
     }
     
     
  
    b.Inorder(root); 
    return 0; 
}

here was the output:

root is 0
hillo is being put in the same node hillo = hi
after insert root is 0xeb7f10
bye is being put in the left node bye < hi
after insert root is 0xeb7f10
chao is being put in the left node chao < hi
chao is being put in the right node chao > by
after insert root is 0xeb7f30
after insert root is 0xeb7f10
elo is being put in the left node elo < hi
elo is being put in the right node elo > by
elo is being put in the right node elo > ch
after insert root is 0xeb7f88
after insert root is 0xeb7f30
after insert root is 0xeb7f10
root is
root is
root is

root is
root is

root is
root is

root is

root is

Gary Strivin' · Accepted Answer · 2021-02-02T12:15:12.443

Problem:

Your nodes are not NULL, but you're not printing the data of any of them. With the statement printVector(data); you're printing just the data of the object b.

Solution:

Change printVector(data); to printVector(root->data);.

Additional information:

using namespace std; is considered a bad practice (More info here).
Instead of creating an object b just to use the methods of the class BST, make the methods static and pass the node as an argument. It's cleaner and will help to avoid confusions as this case.
Personally I would recommend you to use nullptr instead of NULL in C++.
Even if root is NULL, the Inorder method will execute "cout << "root is " << endl;" before returning and therefore outputting unnecesary lines.
You should use delete to free the data you store with new.

thank you, this fixed the issue perfectly. and thanks for the tips, will apply immediately — Joshua John, Feb 02 '21 at 14:59

Binary Search Tree: root remains null during Inorder (C++)

1 Answers1