Succesor AVL tree c++

Question

i've tried to implement succesor of AVL tree, i will not cover all my code, this is the most important part(all other parts 100% works). I have class avltree, struct node with element, left, right and parent. also i have typedef struct node *nodeptr; for easy.

nodeptr avltree::find(int x,nodeptr &p)
{
    if (p==NULL)
    {
        cout<<"NOT EXISTS\n"<<endl;
        return NULL;
    }
    else
    {
        if (x < p->element)
        {
            return find(x,p->left);
            // return p;
        }
        else
        {
            if (x>p->element)
            {
                return find(x,p->right);
                // return p;
            }
            else
            {
                // cout<<"EXISTS\n"<<endl;
                return p;
            }
        }
    }
}
nodeptr avltree::succ(int x, nodeptr &p){
    p=find(x, p);
    if (p->right){
        return findmin(p);
    }
    else {
        while(   (p->parent)->left!=p  ){
            p=p->parent;

        }
        return p;
    }
}

And here, how i define all this stuff in main: int main()

{
    nodeptr root, max;
    avltree bst;
    root=NULL;


    for(int i=0; i<=5; i++){
        bst.insert(i, root);
    }


    bst.getneighbors(root);
    max=bst.succ(3, root);
    cout<<max->element;

    return 0;
}

void avltree::getneighbors(nodeptr &p){ //get parents
    while(!p->left){
        nodeptr p2;
        p2=p->left;
        p2->parent=p;
        getneighbors(p2);
    }
    while(!p->right){
        nodeptr p2;
        p2=p->right;
        p2->parent=p;
        getneighbors(p2);
    }
}

So, i've implemented function getParents. But nothing work, for example succ(3) in compute 0. Can you please help me to figure me out what the problem is. If you need additional code - i will post it. Thanks in advance.

Answer 1

nodeptr avltree::succ(int x, nodeptr &p){
    p=find(x, p);
    if (p->right){
        //////////////////////////
        return findmin(p->right);
        //////////////////////////
    }
    else {
        //////////////////////////
        while(true){
            if (p->parent == NULL)
                return NULL;
            if ((p->parent)->left == p)
                return p->parent;
            else
                p=p->parent;
        }
        //////////////////////////
    }
}