I have implemented a Morris traversal to solve LeetCode problem 98. Validate Binary Search Tree:
Given the
rootof 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?
RISHI MISHRA is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
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
}
};