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

Code:

typedef struct Node {
int ind;
int val;
struct Node *left;
struct Node *right;
} Node;

.. is simple:

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

Code:

while (Node != NULL) {
traverse(Node->left);
}

2. Once at the smallest node, "access" the node and perform whatever action:

Code:

printf("%d", Node->val);

3. Then go back to the previous node and check the right hand node (which is bigger than the left)

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!

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;
}
}
}
}

By the way, tr_insertNode creates a new Node on the heap with the index and value specified, and returns a pointer to it.

Has anyone got any ideas?

Cheers

Will