I'm using Morris inorder traversal to traverse (iterate over all nodes of) a binary tree. The relevant code (inspired by the C code here) looks like this:
#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);
if (current->data < 0) {
/* !!! Add cleanup code here. */
return; /* Stop the traversal. */
}
current = current->right;
}
}
}
This code compiles and works correctly if there are no nodes with negative values. For nodes with negative values, I want to stop the traversal right after the first negative value. However, at that point some of the ->right pointers are broken (see the code line with this breaks in it), and I need to add cleanup code (to the code line with !!! in it) to restore these broken pointers, and make the tree valid again.
My question: What should this cleanup code be?
Please note that I still want to keep the Morris inorder traversal algoritm, because the program runs in a resource-constrained system with a small fixed stack and no dynamic memory available. So replacing the Morris algorithm with another traversal algorithm which doesn't need cleanup, but it uses more memory (e.g. recursive traversal or a traversal with a manually managed path stack) is not a valid answer to my question.
There's likely a better solution to this, but here's something I hacked together. It works by having a new exit variable, which gets flagged when a negative value is read. It then continues running as usual until after the functions's already existing code to revert the changes is ran, at which point it will early exit.
The one flaw of this implementation is that the program will still attempt to process another node before this happens, if the negative value node is not a leaf. Wrapping most of the process_node label's code in an if (!exit) so that it doesn't get processed when it's trying to exit fixes this.
void traverse(struct node *root) {
struct node *current = root;
struct node *pre;
int exit = 0;
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;
if (exit) return;
process_node:
if (!exit){
printf("%d ", current->data);
if (current->data < 0) {
/* !!! Add cleanup code here. */
exit = 1;
}
}
current = current->right;
}
}
}