How to do binary search lookups while a Morris inorder traversal is in progress

Question

Morris inoder tree traversal is an inorder traversal of a binary search tree which uses only O(1) memory (and no recursion), but temporarily modifies (and then restores) some of the ->right pointers of the tree.

Example C code (inspired by the C code here):

#include <stdio.h>  /* printf(). */
#include <stdlib.h>  /* NULL. */
struct node {
    struct node *left, *right;
    int data;
};
void traverse(struct node *root) {
    struct node *current = root;
    struct node *pre;
    while (current != NULL) { 
        if (current->left == NULL) goto process_node;
        /* Find the inorder predecessor of current */
        pre = current->left;
        while (pre->right != NULL && pre->right != current) {
            pre = pre->right;
        }
        if (pre->right == NULL) {
            /* Make current the right child of its inorder predecessor */
            pre->right = current;  /* This breaks the tree temporarily. */
            current = current->left;
        } else {
            /* Revert the changes made in the 'if' part to restore the
             * original tree i.e., fix the right child of predecessor.
             */
            pre->right = NULL;
          process_node:
            printf("%d ", current->data);
            /* find(root, current->data + 2); */
            /* find(root, current->data - 2); */
            current = current->right;
        }
    }
}

However, because of the temporary modifications, additional binary tree value lookups don't work. For example, if we uncomment the find(...) calls here, then the following naïve find implementation will fall to an infinite loop if called during the traversal:

int datacmp(int a, int b) {  /* Increasing order: -1 means less (a < b). */
    return a < b ? -1 : a > b;
}

struct node *find(struct node *root, int data) {
    struct node *explore = root;
    int c;
    while (explore != NULL) {
        c = datacmp(data, explore->data);
        if (c == 0) {
            return explore;
        } else if (c < 0) {
            explore = explore->left;
        } else {
            explore = explore->right;
        }
    }
    return NULL;
}

Is there an implementation of find which works even during the Morris inorder traversal?

Answer 1

This implementation of find works outside and during Morris inorder traversal:

int datacmp(int a, int b) {  /* Increasing order: -1 means less (a < b). */
    return a < b ? -1 : a > b;
}

struct node *find(struct node *root, int data) {
    struct node *explore = root;
    struct node *milestone = NULL;
    int c;
    while (explore != NULL) {
        c = datacmp(data, explore->data);
        if (c == 0) {
            return explore;
        } else if (c < 0) {
            milestone = explore;
            explore = explore->left;
        } else {
            explore = explore->right;
            /* Stop on circular path created by a Morris inorder traversal. */
            if (explore == milestone) break;
        }
    }
    return NULL;
}

This implementation of binary search tree lookup is still O(depth), but it detects and stops on circular paths created by a pending Morris inorder traversal. It works like this: Such a circular path starts with a node (let's call it milestone), then the path moves left, then the path moves right at least once, reaching the milestone node again. The implementation above records the current node as milestone before each left move, and it checks for reaching the milestone node after each right move.