non-recursive Iterator for Binary search tree

Question

I have a main.c file similar to this:

it = bet_create_iterator(bstree);

while ((n = bst_iter_next(it))) {
    printf("value: %d", bst_getvalue(n));
}

I hope you can see from the above how its used. Heres my problem though. its that function,

bst_iter_next(it)

it returns a pointer to a node in the tree.

I find it really simple to traverse a BST recursively but doing it this way, returning a node each time is proving difficult.

If someone could help a guy out and explain to me how to do it it would be much appreciated.

Cheers,

Andy.

Answer 1

Have it be a node double pointer and every time you call bst_iter_next(it) point it to the next node in line. Lets say that you are traversing the tree in post order and call it = bet_create_iterator(bstree);. Now your it points to the root node. Next you call bst_iter_next(it);. It will do something like this:

bst_iter_next(node **it) {
    if (*it has children) {
       *it = *it->left;
       return *it
    }
    else if (*it->parent == NULL)
        *it = NULL or whatever;
        return NULL;
    else {
       node *n = *it;
       while(1) {
          if(n->parent == NULL) {
             *it = NULL or whatever;
             return NULL;
          }
          if(n->parent->left == n && n->parent->right!= NULL) {
              *it = n->parent->right;
              return *it;
          }
          else
              n = n->parent;
       }
    }
}

Anyway, that seems to work in my mind, but my logic may be flawed.

Answer 2

Here is one way I did it:

struct node{
    int value;
    struct node *left, *right, *parent;
    int visited;
};

struct node* iter_next(struct node* node){
    struct node* rightResult = NULL;

    if(node==NULL)
        return NULL;

    while(node->left && !(node->left->visited))
        node = node->left;

    if(!(node->visited))
        return node;

    //move right
    rightResult = iter_next(node->right);

    if(rightResult)
        return rightResult;

    while(node && node->visited)
        node = node->parent;

    return node;
}

The trick is to have both a parent link, and a visited flag for each node. Also, iter_next() must be called without the state of the tree structure changing (of course), but also that the "visited" flags do not change values.

Here is the tester function that calls iter_next() and prints the value each time for this tree:

                  27
               /      \
              20      62
             /  \    /  \
            15  25  40  71
             \  /
             16 21

int main(){

    //right root subtree
    struct node node40 = {40, NULL, NULL, NULL, 0};
    struct node node71 = {71, NULL, NULL, NULL, 0};
    struct node node62 = {62, &node40, &node71, NULL, 0};

    //left root subtree
    struct node node16 = {16, NULL, NULL, NULL, 0};
    struct node node21 = {21, NULL, NULL, NULL, 0};
    struct node node15 = {15, NULL, &node16, NULL, 0};
    struct node node25 = {25, &node21, NULL, NULL, 0};
    struct node node20 = {20, &node15, &node25, NULL, 0};

    //root
    struct node node27 = {27, &node20, &node62, NULL, 0};

    //set parents
    node16.parent = &node15;
    node21.parent = &node25;
    node15.parent = &node20;
    node25.parent = &node20;
    node20.parent = &node27;
    node40.parent = &node62;
    node71.parent = &node62;
    node62.parent = &node27;

    struct node *iter_node = &node27;

    while((iter_node = iter_next(iter_node)) != NULL){
        printf("%d ", iter_node->value);
        iter_node->visited = 1;
    }
    printf("\n");
    return 1;
}

Which will print the values in sorted order:

15 16 20 21 25 27 40 62 71