Memory leaks in binary tree

[Txcz]

Hi, i programmed some kind of wierd binary search tree, it works fine, not fast enought but with no mistakes, but there are some memory leaks and i can not find where there are, i even tried to wrote my own counter and it tells that everything was correctly deleted but using valgrind there are still some memory leaks.

Leaf represents every leaf of tree, it holds a value of list
Node represents every other inner nodes, it do not hold real value, but just value for faster search
Root its just root node, it does not occur anywhere else

#include <cstdlib>
#include <typeinfo>
#include <iostream>
#include <vector>
#include <iterator>

using namespace std;

template<typename E>
class Place {
    Place<E> *pre;
    E value;
public:
    static int count;
    Place(Place<E>*a) : pre(a) {}
    virtual ~Place() {pre = NULL;}
    virtual void insert(E&) = 0;
    virtual void print(int) = 0;
    virtual void setR(Place<E> *) = 0;
    virtual void setL(Place<E> *) = 0;
    virtual Place<E>* getR() = 0;
    virtual Place<E>* getL() = 0;
    virtual int found(E&, int, const bool&) = 0;
    virtual void remove(E&) = 0;
    virtual Place<E>* go(E&, const bool&) = 0;
    virtual void goUp(E&, E&) = 0;
    virtual int getNum() = 0;
    virtual void vecMake(vector<E> &a, int &i) = 0;
    virtual void clean()=0;

    virtual Place<E> *getPre() {return pre;}
    virtual void setPre(Place<E> *a) {pre = a;}
    virtual  E& getVal() {return value;}
    virtual void setVal(E& i) {value = i;}
    virtual bool equals(Place<E> *a) {return a == this;}
    virtual bool equals(E& i){return this->getVal() == i;}
};
template <typename E>int Place<E>::count = 0;

template<typename E>
class Node : public Place<E> {
    Place <E>*left;
    Place <E>*right;
public:
    Node(Place <E>*a) : Place<E>::Place(a) {}
    virtual ~Node() { Place<E>::count--;
        if(left != NULL){delete left;}
        if(right != NULL){delete right;}}
    virtual void setL(Place<E>* a) {left = a;}
    virtual void setR(Place<E>* a) {right = a;}
    virtual void print(int i) {
        left->print(i+1);
        cout << "<" << this->getVal()<<"|"<<i<< ">";
        right->print(i+1);
    }
    virtual void insert(E& i) {go(i, true)->insert(i);}
    virtual Place<E>* getR() {return right;}
    virtual int found(E& i, int j, const bool &b) {return go(i, true)->found(i, j+1, b);}
    virtual void remove(E& i) {go(i, true)->remove(i);}
    virtual Place<E>* go(E& i, const bool &b) {
        if (b) {if (i >= this->getVal()) return right;
            else return left;
        } else {if (i >= this->getVal()) return left;
            else return right;
        }}
    virtual void goUp(E &i, E &j) {
        if (this->equals(i)){
            this->setVal(j);
            return;
        }this->getPre()->goUp(i, j);
    }
    virtual Place<E>* getL() { return left;}
    virtual int getNum() {return -1;}
    virtual void vecMake(vector<E>& a, int &i) {
        left->vecMake(a, i);
        right->vecMake(a, i);
    }

};

template <typename E>
class Leaf : public Place<E> {
    int numbers;
public:
    Leaf(Place <E>*a) : Place<E>::Place(a) {numbers = 1;}
    virtual ~Leaf() {Place<E>::count--;}
    virtual void clean(){delete this;}
    virtual void print(int i) {cout << this->getVal();}
    virtual void setR(Place <E>*) {return;}
    virtual void setL(Place <E>*) {return;}
    virtual void insert(E &i) {
        if (this->equals(i)) {
            numbers++;
            return;
        }Place<E>::count+=2;
        Place <E>*pom = new Node<E> (this->getPre());
        Place <E>*tmp = new Leaf<E> (pom);
        tmp->setVal(i);
  
        this->setPre(pom);
        if (i < this->getVal()) {
            pom->setL(tmp);
            pom->setR(this);
            pom->setVal(this->getVal());
        } else {
            pom->setL(this);
            pom->setR(tmp);
            pom->setVal(i);
        }
        if (pom->getPre()->getR()->equals(this)) {
            pom->getPre()->setR(pom);
        } else pom->getPre()->setL(pom);
    }

    virtual Place<E>* getR() {return NULL;}
    virtual int found(E &i, int j, const bool &b) {
        if (!this->equals(i)){
            if(!b) return -1;
            else return 0;
        }
        if (b) return numbers;
        return j;
    }

    virtual void remove(E &i) {
        if (!this->equals(i)) return;
        if (numbers != 1) {//this->getVal() == i && 
            numbers--;
            return;
        }
        Place<E>*omg = this->getPre();
        Place<E>*tmp = omg->getPre();
        Place<E>*pom=omg->go(i, false);
        if (tmp->getVal() > i) {
            tmp->setL(pom);
        } else tmp ->setR(pom);
        pom->setPre(tmp);
        pom->goUp(i, this->getPre()->getVal());
        tmp = NULL;
        pom = NULL;
        
        if(omg->getVal()>i){
            omg->setR(NULL);
        }else omg->setL(NULL);
        delete omg;
    }

    virtual Place<E>* go(E&, const bool&) {return NULL;}
    virtual void goUp(E &i, E &j) {this->getPre()->goUp(i, j);}
    virtual Place<E>* getL() {return NULL;}
    virtual int getNum() {return numbers;}
    virtual void vecMake(vector<E>& a, int &i) {
        a.push_back(this->getVal());
        i++;
    }
};

template<typename E>
class Root : public Place<E> {
    Place<E> *next;
public:
    Root():Place<E>::Place(NULL){next = NULL;}
    virtual ~Root(){
        Place<E>::count--;
        if(next != NULL){
             delete next;
        }
    }

    virtual void insert(E& i){
        if (next == NULL) {
            next =  new Leaf<E> (this);
            next->setVal(i);
            Place<E>::count++;
            return;
        }next->insert(i);
    }
    virtual void print(int i){
        if(next == NULL) return;
        next->print(i);
    }
    virtual void setR(Place<E> * a){next = a;}
    virtual void setL(Place<E> * a){next = a;}
    virtual Place<E>* getR(){return next;}
    virtual Place<E>* getL(){return next;}
    virtual int found(E &i, int j, const bool &b){
        if(next == NULL){
            if(b){return 0;}
            else {return -1;}}
        return next->found(i, j, b);
    }
    virtual void remove(E &i){
        if(next == NULL) return;
        if((typeid(*next) == typeid(Leaf<E>)) && (next->equals(i)) && (next->getNum() == 1)){
            delete next;
            next = NULL;
            return;
        }next->remove(i);
    }
    virtual Place<E>* go(E&, const bool&){return next;}
    virtual void goUp(E&, E&){return;}
    virtual int getNum(){return -1;}
    virtual void vecMake(vector<E> &a, int &i){
        if(next == NULL) return;
        next->vecMake(a,i);
    }
        
};

template<typename E>
class BSTSET{
    Place<E> *root;
    int p;
    int size;
    vector<E> a;
public:
    class iterator {
        vector<E> vec;
        int val;
    public:
        iterator(vector<E> a, int i):vec(a),val(i){}
        iterator& operator++() {
            ++val;
            return *this;
        }
        iterator operator++(int) {
            iterator tmp(*this);
            operator++();
            return tmp;
        }
        bool operator==(const iterator& rhs) {return val == rhs.val;}
        bool operator!=(const iterator& rhs) {return val != rhs.val;}
        E& operator*() {return vec[val];}
    };
    iterator& begin() {
        vecMake();
        p = 0;
        iterator tmp();
        return (*new iterator(a,p));
    }
    iterator& end() {return (*new iterator(a,size));}
    BSTSET() {
        Place<E>::count++;
        root = new Root<E>();
        size = 0;
    }

    ~BSTSET() {clear();}
    void clear(){
        cout<<"count: "<<Place<E>::count<<"\n";
        delete root;
        cout<<"count: "<<Place<E>::count<<"\n";
    }
    void insert(E i) {root->insert(i);}
    void remove(E i) {root->remove(i);}
    void print() {root->print(1);}
    int getDeep(E i) {return root->found(i, 1, false);}
    int getNum(E i) {return root->found(i, 1, true);}
    void operator <<(E i) {insert(i);}
    int operator[](E i) {return getDeep(i);}
    int operator()(E i) {return getNum(i);}
    void operator >>(E i) {remove(i);}
    friend ostream& operator <<(ostream& os, BSTSET& bst) {
        bst.print();
        return (os);
    }
    void vecMake() {root->vecMake(a, size);}
};

[Txcz]

By searching, i was able to find where leaks were created, but i still cannot figure why, and how to prevent it.

BSTSET<int> a;

for (BSTSET<int>::iterator it = a.begin(); it != a.end(); it++) {
            cout << (*it) << " ";
        }