Trying to create new instance of class using template, unexpected error

Question

Trying to make a B inary S earch T ree (BST for short) using a template.

When I try to create a new instance of my BST I get an unexpected error. I hope the solution does not involve pointers since I would like to keep them at a minimum.

For now I have:

template <typename Type>
class BST {                 // The binary search tree containing nodes
private:
    BSTNode<Type> *root;    // Has reference to root node

public:
    BST ();
    bool add (int, Type);
};

And the Node type:

EDIT: When I cut out code to un-encumber text, I forgot the constructor, now it's been added

template <typename Type>
class BSTNode {    // Binary Search Tree nodes
private:
    int key;       // we search by key, no matter what type of data we have
    Type data;
    BSTNode *left;
    BSTNode *right;

public:
    BSTNode (int, Type&); 
    bool add (int, Type);
};

EDIT2: Here is the actual constructor

template <typename Type>
BSTNode<Type>::BSTNode (int initKey, Type &initData) {
     this->key = initKey;
     this->data = initData;
     this->left = NULL;
     this->right = NULL;
}

I want to try and test if anything works / doesn't work

BSTNode<int> data = new BSTNode (key, 10);

And I get: Expected type specifier before BSTNode. I have no idea what I'm doing wrong, but one thing I do hope is I don't have to use data as a pointer.

BSTNode<int> data = new BSTNode<int> (key, 10);

Also does not work, seems it believes < int > is < & int> and it doesn't match

Solution

First, you need to fully specify the type on the RHS of the assignment, and, since you are instantiating a dynamically allocated node with new, the LHS should be a pointer:

BSTNode<int>* data = new BSTNode<int> (key, 10);
            ^                     ^

If you don't need a node pointer, then use

BSTNode<int> data(key, 10);

Second, your BSTNode<T> class doesn't have a constructor taking an int and a Type, so you need to provide that too.

template <typename Type>
class BSTNode {
 public:
  BSTNode(int k, const Type& val) : key(k), data(val), left(0), right(0) { .... }
};