So the algorithm to traverse a binary search tree structure in C:

.. is simple:Code:typedef struct Node { int ind; int val; struct Node *left; struct Node *right; } Node;

1. Traverse down to the smallest value by calling the traversal recursively:

2. Once at the smallest node, "access" the node and perform whatever action:Code:while (Node != NULL) { traverse(Node->left); }

3. Then go back to the previous node and check the right hand node (which is bigger than the left)Code:printf("%d", Node->val);

Code:traverse(Node->right);

My question is... I have two binary search trees with the data structure defined above.

Each node of the tree has an index and a value.

I want to go through and add up the values for each index, without having to repeatedly search the tree.

(ie. I don't want to loop for every index... I only want to traverse each tree once).

Is there any way of doing this in C? I haven't seen this anywhere else on the web. An idea I had was this code, but I've got stuck.. this one's really confusing me!

By the way, tr_insertNode creates a new Node on the heap with the index and value specified, and returns a pointer to it.Code:INPUT: Pointers to binary trees A and B OUTPUT: Pointer to tree n, the sum of A and B Node *add(Node *a, Node *b, Node *n) { // loop through a,b and add while (a!=NULL) { n = add(a->left, b, n); while (b!=NULL) { n = add(a, b->left, n); if (a->ind == b->ind) { n = tr_insertNode(n, a->ind, (a->val + b->val)); } else if (a->ind > b->ind) { b = b->previous; n = add_row(a->right, b, n); } else { a = a->previous; } } } }

Has anyone got any ideas?

Cheers

Will