Redefining a structure defined in a base class from a derived class

Viewed 827

I've made a class(named BST) for Binary Search Tree in C++ and now trying to make a class(named AVL) for AVL trees that inherits the BST class. I've defined a structure(named node) inside my BST class and now would like to add an extra member 'height' to it when using it in the derived AVL class. I can't find a way how to redefine the structure and add an extra member to it only while it is being used for the AVL class. Here is my code for BST class:

class BST
{
protected:
struct node
{
    int val;
    node* left;
    node* right;
};
node* root;

public:
BST()
{
    this->root = NULL;
}
void insert(int val);
void display();
void displayPretty();
void displaySorted();
int min();
int max();
int height();
void remove(int val);
int after(int val);
int before(int val);
static bool isBST(BST tree);
~BST()
{
    removeAll(this->root);
}

protected:
node* create(int val);
node* insertInto(node* root,int val);
void displayLevelOrder(queue<node*>* q);
void displayPretty(node* p, int indent);
void displayInorder(node* root);
node* getMin(node* root);
node* getMax(node* root);
int heightOf(node* root);
node* removeFrom(node* root,int val);
void removeAll(node* root);
node* getSuccessorOf(int val,node* root,node* prev);
node* getPredecessorOf(int val,node* root,node* next);
static bool isBST(node* root,int min,int max);

};

And my incomplete code for AVL class is :

class AVL : public BST
{
protected:
struct node
{
    // redefine node here (by adding the 'height' member)
    // such that all the node variables/pointers in BST (e.g. root)
    // also get created with this new definition
};

public:
AVL() : BST(){} 
void insert(int val);
void remove(int val);

private:
node* insertInto(node* root,int val);
node* removeFrom(node* root,int val)

};

I've tried using structure inheritance like this:

struct avlnode : node
{
    int height;
};

But the problem here is avlnode->left and avlnode->right are being node* type instead of avlnode* type and thus I can't access the height member from them.

Any help would be appreciated :D

2 Answers
Related