// morris traverse
class Solution {
   public:
    bool isValidBST(TreeNode* root) {
        int64_t vlast = INT64_MIN;
        TreeNode* curr = root;
        TreeNode* predecessor = nullptr;
        while (curr != nullptr) {
            predecessor = curr->left;
            if (predecessor != nullptr) {
                while (predecessor->right != nullptr && predecessor->right != curr) {
                    predecessor = predecessor->right;
                }
                if (predecessor->right == nullptr) {
                    predecessor->right = curr;
                    curr = curr->left;
                } else {
                    predecessor->right = nullptr;

                    if (curr->val <= vlast) return false;
                    vlast = curr->val;

                    curr = curr->right;
                }
            } else {
                if (curr->val <= vlast) return false;
                vlast = curr->val;

                curr = curr->right;
            }
        }

        return true;
    }
};