1
\$\begingroup\$

So far I have attempted to find the inorder successor through recursion and it seems to be working right. Can someone review the code and give suggestions?

struct node
{
    int data;
    struct node* left;
    struct node* right;
};

struct node * inOrderSuccessor(struct node *root, struct node *n)
{
    if(root == NULL)
        return NULL;

    static node *successor = NULL;
    if(root->data >= n->data)
    {
        successor = root;
        successor->data = root->data;
    }

    if(root->right !=NULL && n->data >= root->data)
        return inOrderSuccessor(root->right,n);

    if(root->left != NULL && n->data < root->data)
        return inOrderSuccessor(root->left ,n);

    return successor;
}

    struct node* newNode(int data)
    {
        struct node* node = (struct node*)malloc(sizeof(struct node));
        node->data   = data;
        node->left   = NULL;
        node->right  = NULL;

        return(node);
    }

    int main()
    {
        struct node *temp, *succ,*successor=NULL;
        struct node *root = newNode(20);
        root->left        = newNode(8);
        root->left->left  = newNode(4);
        root->right       = newNode(22);
        root->left->right = newNode(12);
        root->left->right->left=newNode(10);
        root->left->right->right=newNode(14);


        temp = root->left->left;

        succ =  inOrderSuccessor(root, temp);
        if(succ !=  NULL)
            printf("\n Inorder Successor of %d is %d ", temp->data, succ->data);   
        else
            printf("\n Inorder Successor doesn't exit");

        getchar();
        return 0;
    }
\$\endgroup\$
  • \$\begingroup\$ Does it work for a tree with these nodes: 16, 12, 10, 8, 11 ? Inorder successor of 11 seems to return 11, but should return 12. \$\endgroup\$ – Software Engineer Sep 11 '15 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.