Stack template has some logical error for implementing binary tree

Question

i have a template of stack and a template of TreeNode (Binary Tree). Following is the code of two classes (stack and TreeNode). I succesfully inserted data into tree by using insert() function but there is a problem while retrieving it back using stack. Following are the compile time errors:

Error 1 error C2143: syntax error : missing ';' before '*' c:\users\computer house\desktop\tree 1\tree 1\source.cpp 8 1 Tree 1

Error 2 error C4430: missing type specifier - int assumed. Note: C++ does not support default-int c:\users\computer house\desktop\tree 1\tree 1\source.cpp 8 1 Tree 1

#include<iostream>
#include<stdlib.h>
using namespace std;

template<class T>
class Stack{
private:
    TreeNode<T> *headNode, *pastCurrentNode;

public:
    Stack(){
        headNode = new TreeNode<T>;
        headNode=NULL;
    }

    void push(T x){
        TreeNode<T>* newNode = new TreeNode<T>;
        newNode->set(x);

        if(headNode != NULL){
            newNode->setNext(headNode);
            pastCurrentNode=headNode;
            headNode=newNode;
        }
        else{
            headNode=newNode;
            pastCurrentNode=headNode;
        }
    }

    T pop(){
        TreeNode<T>* p = new TreeNode<T>;
        p = headNode;
        headNode = pastCurrentNode;
        T x = p->get();
        delete p;
        return x;
    }

    T top(){return headNode->get();}

    bool isEmpty(){return (headNode == NULL);}
};

template<class T>
class TreeNode{
private:
    TreeNode* right, *left;
    T* object;


public:
    TreeNode(){
        this->left = this->right = NULL;
        object = NULL;
    }

    TreeNode(T* object){
        this->object  = object;
        this->left = this->right = NULL;
    }

    T* getInfo(){
        return this->object;
    }

    void setInfo(T* object){
        this->object = object;
    }

    TreeNode* getLeft(){return this->left;}
    void setLeft(TreeNode* left){this->left = left;}
    TreeNode* getRight(){return this->right;}
    void setRight(TreeNode* right){this->right = right;}

    int isLeaf(){
        if(this->left==NULL && this->right == NULL){
            return 1;
        }
        return 0;
    }

};


void insert(TreeNode<int>* root, int* info){
    TreeNode<int>* newNode = new TreeNode<int>(info);
    TreeNode<int>*p, *q;

    p = q = root;

    while(*info != *p->getInfo() && q != NULL)
    {
        p = q;

        if(*info < *p->getInfo())
            q = p->getLeft();
        else 
            q = p->getRight();

    }

    if(*info == *p->getInfo()){
        cout<<"Error: Duplication: "<<*info<<endl;
        delete newNode;
    }
    else if(*info < *p->getInfo()){
        p->setLeft(newNode);
    }
    else{
        p->setRight(newNode);
    }
}



void sInOrder(TreeNode<int>* root){
    Stack< TreeNode<int>* > stack;
    TreeNode<int>* p;

    p=root;

    do{
        while(p != NULL){
            stack.push(p);
            p = p->getLeft();
        }
        //At this point left tree is empty

        if(! stack.isEmpty()){
            p = stack.pop();
            cout<<*p->getInfo()<<" ";
            //go back and traverse right subtree
            p = p->getRight();
        }
    }
    while(!stack.isEmpty() || p!=NULL);

}

int main(){

    int x[]={14,15,4,9,7,18,3,5,16,4,20,17,9,14,5,-1};
    TreeNode<int>* root = new TreeNode<int>;

    root->setInfo(&x[0]);

    for(int i=1; x[i]>0; i++){
        insert(root, &x[i]);
    }

    cout<<"\nStacked In Order: "; sInOrder(root);
    cout<<endl;


    system("pause");
}

Answer 1

You have:

TreeNode<T> *headNode, *pastCurrentNode;

but TreeNode is not declared prior to that line. You need to add either a forward declaration of TreeNode or the full definition of TreeNode before you can use TreeNode<T>* headNode.

Forward declaration:

template <class T> class TreeNode;

will suffice for the declarations of headNode and pastCurrentNode. However, it won't suffice for

Stack(){
    headNode = new TreeNode<T>;
    headNode=NULL;  // This is a problem anyway.
                    // You have just leaked memory.
}

In order to be able to use

    headNode = new TreeNode<T>;

you need the full definition of TreeNode.

Since TreeNode does not depend on Stack, my advice to you would be to move the complete definition of TreeNode before the definition of Stack.

Update, in response to OP's comment

// Define TreeNode first.

template<class T>
class TreeNode{
private:
    TreeNode* right, *left;
    T* object;


public:
    TreeNode(){
        this->left = this->right = NULL;
        object = NULL;
    }

    // Add rest of TreeNode definition
};

// Now define Stack.

template<class T>
class Stack{
private:
    TreeNode<T> *headNode, *pastCurrentNode;

public:
    Stack(){
        headNode = new TreeNode<T>;
        headNode=NULL;
    }

    // Add rest of Stack definition

};

PS I noticed that you are using

    TreeNode<T>* newNode = new TreeNode<T>;
    newNode->set(x);

in Stack::push. However, there is no set function in TreeNode. You need to update your code appropriately for that to work.