Basic "BST": getting error unresolved external symbol

[mrpear2020]

Hello gurus, can you please help me figure out this error:
Goal: Create a Binary Search Tree and add "1" to the root node.
The error I am getting is:
unresolved external symbol "public:_thiscall BST::BST(void)"

 #include <iostream>

using namespace std;

struct BST {
	int data;
	BST* root;
	BST* left;
	BST* right;

	//Default Constructor
	BST();
	
	BST(int value);

	//Insert 
	BST* Insert(BST*, int);
};

BST::BST(int value) {
	//Initialize root, right child and left child
	root = nullptr;
	right = nullptr;
	left = nullptr;
}
//Insert function
BST* BST::Insert(BST* root, int value)
{
	//Check if root is non existent
	if (root == nullptr) {
		//it means node is empty. Assign value to the data value
		root->data = value;
	}
	//Return the value
	return root;

}

 
int main() {
        //Create object
	BST mybst, * root = nullptr;
        //use method insert here
	mybst.Insert(root, 1);
	

}

[lastchance]

You have declared a constructor taking no arguments (on line 12), but you haven't actually defined that function.

On the other hand, your constructor taking one argument, which is defined starting line 20, doesn't actually do anything with that argument.

You can also avoid defining root in main.

[dutch]

You need to define a separate Node struct.

class BST {

    struct Node {
        int   data;
        Node* left;
        Node* right;

        Node(int data) : data(data), left{}, right{} {}
    };

    Node* root;

public:

    BST() : root{} {}
    ~BST();
    
    void insert(int data);
};

[jonnin]

^^ I don't see why you wanted to do that here (it works, but so would just making his ctor body and fixing the issues mentioned). Do you mind explaining?

[dhayden]

Jonnin, I agree with dutch. The OP has data, right, left, and root in the BST class. A node doesn't need a pointer to root, and a tree doesn't need data, right or left.

mrpear2020, line 30 checks for a nullptr. Line 32 then accesses the pointer that is guaranteed to be null. That won't work....

[dutch]

jonnin wrote:

Do you mind explaining?

I think you must not have looked at the situation closely enough. As dhayden said there is no reason to have a root pointer in every single node. And an overall class for the tree (list, queue,...) is always a good idea. Here it is filled out a little more:

#include <iostream>

class BST {

    struct Node {
        int   data;
        Node* left;
        Node* right;
        Node(int data) : data(data), left{}, right{} {}
    };

    static void print(Node* nd);
    static void clear(Node* nd);

    Node*  mRoot;
    size_t mSize;

public:

    BST() : mRoot{}, mSize{} {}
    ~BST() { clear(); }
    
    void   insert(int data);
    void   clear() { clear(mRoot); }
    void   print() const { print(mRoot); std::cout << '\n'; }
    size_t size() const { return mSize; }
};

void BST::insert(int data) {
    Node** nd = &mRoot;
    while (*nd)
        nd = data < (*nd)->data ? &(*nd)->left : &(*nd)->right;
    *nd = new Node(data);
    ++mSize;
}

void BST::clear(Node* nd) {
    if (!nd) return;
    clear(nd->left);
    clear(nd->right);
    delete nd;
}

void BST::print(Node* nd) {
    if (!nd) return;
    print(nd->left);
    std::cout << nd->data << ' ';
    print(nd->right);
}

int main() {
    BST bst;
    for (int n: {6, 3, 4, 8, 7, 9, 0, 2, 5, 1})
        bst.insert(n);
    std::cout << "size: " << bst.size() << '\n';
    bst.print();
}

[mrpear2020]

Thanks Dutch and all.
Can you confirm why you used {} {} on this line?
(…)
Node(int data) : data(data), left{}, right{} {} //<== Why double {} {}?
(…)

[dutch]

The last set of braces is the empty function body.