jeudi 7 juillet 2022

Kth Smallest Element in a BST: Stack overflow

I am trying to solve Kth smallest element in a BST, but while running it is showing me this runtime error: AddressSanitizer: DEADLYSIGNAL ==32==ERROR: AddressSanitizer: stack-overflow on address0x7ffc4ae8aff8 .... I have tried dubbing it and got to know that if I am removing this part

""ctr++;

if(ctr==k)

 return cur->val;

""

which is occurring twice in the code, then it not showing this error. I am not able to understand why it is happening. I am using morris traversal for this problem my c++ code below:

class Solution {

public:

int kthSmallest(TreeNode* root, int k) {

    TreeNode* cur=root;

    int ctr=0;

    while(cur!=NULL)

    {

        if(cur->left==NULL)

        {

            ctr++;

            if(ctr==k)

                return cur->val;


            cur=cur->right;

        }

        else

        {

            TreeNode* pre=cur->left;

            while(pre->right!=NULL && pre->right!=cur)

            {

                

                pre=pre->right;

            }

            if(pre->right==NULL)

            {

                pre->right=cur;

                cur=cur->left;

            }

            else

            {

                ctr++;

                if(ctr==k)

                    return cur->val;

                pre->right=NULL;

                cur=cur->right;

            }

        }

    }

    return -1;

}

};

Aucun commentaire:

Enregistrer un commentaire