Binary Search Tree With Templates

[hbcpp]

I have written a working binary search tree, then I went on to change it so that it working with different types. All is well excep for one line that stops the program from compiling.

#Include <iostream>

using namespace std;

template<typename T>
struct Node
{
public:
    Node<T> *pLeft;
    Node<T> *pRight;
    T val;

    Node<T>(T val)
    {
        this->val = val;
        pLeft = pRight = nullptr;
    }
};

template<typename T>
class Tree
{
    Node<T> *root;

    Node<T> *insert_at_sub(T i, Node<T> *p);
    void print_sub(Node<T> *p);
    int t_size = 0;

public:
    Tree ()
    {
        root = nullptr;
    }

    void add(T i)
    {
        ++t_size;
        root = insert_at_sub(i, root);
    }
    void print()
    {
        print_sub(root);
    };

    bool contain(T i)
    {
        return contain_sub(i, root);
    }
    bool contain_sub(T i, Node<T> *p);

    void test()
    {
        cout << root->pRight->pRight->pRight->pLeft->pRight->val << endl;
    }

    int get_size()
    {
        return t_size;
    }
};

template<typename T>
Node* Tree<T>::insert_at_sub(T i, Node<T> *p) // this is where the error occurs
{
    if( ! p )
        return new Node<T>(i);
    else if (i <= p->val)
        p->pLeft = insert_at_sub(i, p->pLeft);
    else if (i > p->val)
        p->pRight = insert_at_sub(i, p->pRight);

    return p;
}

template<typename T>
void Tree<T>::print_sub(Node<T> *p)
{
    if(p)
    {
        print_sub(p->pLeft);
        cout << p->val << endl;
        print_sub(p->pRight);
    }
}

template<typename T>
bool Tree<T>::contain_sub(T i, Node<T> *p)
{
    if (!p)
        return false;
    else if(i == p->val)
        return true;
    else if (i <= p->val)
        contain_sub(i, p->pLeft);
    else
        contain_sub(i, p->pRight);
}

int main()
{
    Tree<int> tr;

    tr.add(4);
    tr.add(6);
    tr.add(1);
    tr.add(9);
    tr.add(2);
    tr.add(0);
    tr.add(89);
    tr.add(12);
    tr.add(32);
    tr.add(5);
    tr.add(22);

    tr.print();

    return 0;
}

The error occurs in the line 59
the error that this program produces:
error: deduced class type 'Node' in function return type

[lastchance]

The error probably comes from line 21, which isn't fully templated. For int write T.

On line 59 the return type should be Node<T>*
i.e. you need to template that also.

Please include the relevant #includes when you post code.

[hbcpp]

I corrected that line but the problem continues the same.

[lastchance]

I was editing my post to include a comment about line 59. Have you done that also?

[lastchance]

To confirm:

Line 21, currently
Node<T> *insert_at_sub(int i, Node<T> *p);
should be:
Node<T> *insert_at_sub(T i, Node<T> *p);


Line 59, currently
Node* Tree<T>::insert_at_sub(T i, Node<T> *p)
should be
Node<T>* Tree<T>::insert_at_sub(T i, Node<T> *p)


Please make sure that you have the relevant headers to allow us to compile this online. In this instance, to avoid other changes in your code, you require

#include <iostream>
using namespace std;

The output (on cpp.sh) is then

0
1
2
4
5
6
9
12
22
32
89

[hbcpp]

@lastchance Thanks it works.