Morris traversal leads to exception on LeetCode: address sanitizer , stack overflow

I have implemented a Morris traversal to solve LeetCode problem 98. Validate Binary Search Tree:

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

My code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        long  aa = LONG_MIN;
        long  bb = LONG_MIN;
        TreeNode* cur = root;
        while(cur){
            if(cur->left == NULL){
                aa = max(aa, bb);
                bb = cur->val;
                if(aa != LONG_MIN && aa >= bb) return false;
                cur = cur->right;
            }
            else{
                TreeNode* prev = cur->left;
                while(prev->right && prev->right != cur){
                    prev = prev->right;
                }

                if(prev->right == NULL){
                    prev->right = cur;
                    cur = cur->left;
                }
                else{
                    prev->right = NULL;
                    aa = max(aa, bb);
                    bb = cur->val;

                    if(aa != LONG_MIN && aa >= bb) return false;

                    cur = cur->right;
                }
            }
        }
        return true;
    }
};

This is a standard Morris traversal implementation where I have just added a check (at two places in the code) comparing a node's value with that of its inorder predecessor to see if the tree is a valid BST:

if(aa != LONG_MIN && aa >= bb) return false;

Error:

Submitting this code at LeetCode, produces the following error:

AddressSanitizer:DEADLYSIGNAL
=================================================================
==22==ERROR: AddressSanitizer: stack-overflow on address 0x7ffcecdecff8 (pc 0x5627c311bad9 bp 0x7ffcecded010 sp 0x7ffcecded000 T0)
    #0 0x5627c311bad9 in __TreeNodeUtils__::freeTreeHelper(TreeNode*) (solution+0x18cad9)
    #1 0x5627c311bb00 in __TreeNodeUtils__::freeTreeHelper(TreeNode*) (solution+0x18cb00)
    #2 0x5627c311badd in __TreeNodeUtils__::freeTreeHelper(TreeNode*) (solution+0x18cadd)
    #3 0x5627c311bb00 in __TreeNodeUtils__::freeTreeHelper(TreeNode*) (solution+0x18cb00)
    [...]
    #243 0x5627c311bb00 in __TreeNodeUtils__::freeTreeHelper(TreeNode*) (solution+0x18cb00)
    #244 0x5627c311badd in __TreeNodeUtils__::freeTreeHelper(TreeNode*) (solution+0x18cadd)
    #245 0x5627c311bb00 in __TreeNodeUtils__::freeTreeHelper(TreeNode*) (solution+0x18cb00)
    #246 0x5627c311badd in __TreeNodeUtils__::freeTreeHelper(TreeNode*) (solution+0x18cadd)
SUMMARY: AddressSanitizer: stack-overflow (solution+0x18cad9) in __TreeNodeUtils__::freeTreeHelper(TreeNode*)
==22==ABORTING

And if I remove the line that checks the BST property:

if(aa != LONG_MIN && aa >= bb) return false;

...then there is no more error. Why this line is giving the above error?

The error does not occur in your function, but in the LeetCode platform code that frees the memory allocated to the tree after your function has returned.

A Morris traversal mutates the tree, temporarily introducing cycles in it. That means that if you abort that traversal somewhere half-way, you may leave the tree with those cycles, which the caller of your function does not expect to happen. When that calling code tries to clean up (notice the mention of freeTreeHelper in the stack trace), it runs along those cycles, presumably with a recursive function, that never stops traversing the nodes on one of those cycles. This eventually leads to a stack overflow.

To avoid this from happening, make sure you restore the tree to its original state (or at least without having cycles) before you return to the caller.

One way would be to continue the Morris traversal to the end and just keep track of the invalid BST state with a boolean variable.

Like this:

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        long  aa = LONG_MIN;
        long  bb = LONG_MIN;
        bool valid = true; // Add this boolean to keep track of BST validity.
        TreeNode* cur = root;
        while(cur){
            if(cur->left == NULL){
                aa = max(aa, bb);
                bb = cur->val;
                // Don't exit, but just keep track of the validity 
                valid &= aa == LONG_MIN || aa < bb;
                cur = cur->right;
            }
            else{
                TreeNode* prev = cur->left;
                while(prev->right && prev->right != cur){
                    prev = prev->right;
                }

                if(prev->right == NULL){
                    prev->right = cur;
                    cur = cur->left;
                }
                else{
                    prev->right = NULL;
                    aa = max(aa, bb);
                    bb = cur->val;
                    // Don't exit, but just keep track of the validity 
                    valid &= aa == LONG_MIN || aa < bb;

                    cur = cur->right;
                }
            }
        }
        return valid; // return the boolean we have kept updated
    }
};