C++, Kth smallest Element in a Binary search tree

Question

I am trying to find the kth smallest element in a binary search tree using Morris traversal, but unfortunately I am getting Runtime error every time and I am unable to spot the error.

int kthSmallest(TreeNode* root, int k) {
        if(root == NULL) return -1;
        int ans = -1;
        TreeNode* curr = root;
        TreeNode* temp;
        while(curr != nullptr && k>0){
            if(curr -> left == nullptr){
                temp = curr;
                curr = curr -> right;
                k--;
            }
            else{
                TreeNode* pr = curr -> left;
                while(pr -> right != nullptr && pr -> right != curr){
                    pr = pr -> right;
                }
                if(pr -> right == nullptr){
                    pr -> right = curr;
                    curr = curr -> left;
                }
                else if(pr -> right == curr){
                    pr -> right = nullptr;
                    temp = curr;
                    curr = curr -> right;
                    k--;
                }
            }
        }
        return temp -> val;
    }

**Error:**  
AddressSanitizer:DEADLYSIGNAL 
================================================================= 
==22==
ERROR: 
AddressSanitizer: 
stack-overflow on address 0x7ffd97244ff8 
(pc 0x00000037d5d9 bp 0x7ffd97245010 sp 0x7ffd97245000 T0) 
==22==
ABORTING

I am expecting someone to spot the error.

Answer 1

I ran your code on LeetCode (https://leetcode.com/problems/kth-smallest-element-in-a-bst/) and got the same error message, and so I assume it is there that you got it.

The quoted error does not occur in your function, but in LeetCode's test driver code. It happens because your function mutates the tree and does not restore it before returning.

The LeetCode driver code will check the value returned by your function with its own (correct) solution code, passing it the same arguments. But as a Morris traversal temporarily creates cycles in the graph, and your function exits without restoring the original tree, the LeetCode solution code gets into an infinite recursion, leading to the error message you see.

Conclusion: it is not intended that you mutate the tree. If you do, make sure to restore the tree back to its original state.