Traverse two binary search trees in order at the same time

[willm07]

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

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:

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

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

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

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

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!

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

[matsp]

So the index can appear many times, with different values, is that correct?

I guess one way would be to have an array for all the indices, traverse the tree, and do something like:

    arr[node->index] += node->value;

--
Mats

[willm07]

Forgot to say.. index can only appear once for any value, and most indexes don't appear at all.

So a typical tree might contain only 4,26,45 and 74, for example.

Therefore an array representation would waste a huge amount of memory.

I have thought about copying a node index / value representation into a linked list and then going through the list one by one and adding to the second binary tree, but this would involve a lot of lookups on the second tree, so no good :/

The ideal scenario would be to just go through each tree in order and add as you go. There is a similar algorithm here that I found, but this one is for linked lists:

http://eecs.harvard.edu/~ellard/Q-97...20.html#smmAlg

[anon]

Traversing a tree needs recursion (or a stack), so it is "wasting" memory anyway? (And if your trees typically have only about 4 nodes, using a tree over an array is a huge waste of space anyway?)

However, if you just want to traverse it, you don't need to do it in order. Simply follow the left pointer and if at end continue from the next right pointer.

[iMalc]

Do the two trees have the exact same shape? If so, wouldn't this do what you want?

Node *add(Node *a, Node *b)
{
    Node *n = NULL;
    // loop through a,b and add
    if (a != NULL && b != NULL)
    {
        n = tr_insertNode(a->ind, (a->val + b->val));

        n->left = add(a->left, b->left);
        n->right = add(a-right, b->right);
    }
    return n;
}

Or will the trees have the same indexes but are linked differently?
Or can the trees even have different indexes in them?

[willm07]

Traversing a tree needs recursion (or a stack), so it is "wasting" memory anyway? (And if your trees typically have only about 4 nodes, using a tree over an array is a huge waste of space anyway?)

However, if you just want to traverse it, you don't need to do it in order. Simply follow the left pointer and if at end continue from the next right pointer.

Yes but recursion is using a stack which will never be filled with all the data from the tree at the same time (as when a function finishes recursion, its value is removed) and therefore will never take up the same amount of memory as an array representation.

Do the two trees have the exact same shape? If so, wouldn't this do what you want?
Code:
Node *add(Node *a, Node *b)
{
Node *n = NULL;
// loop through a,b and add
if (a != NULL && b != NULL)
{
n = tr_insertNode(a->ind, (a->val + b->val));

n->left = add(a->left, b->left);
n->right = add(a-right, b->right);
}
return n;
}
Or will the trees have the same indexes but are linked differently?
Or can the trees even have different indexes in them?

That is the problem.. the trees will not have the same indexes in them, and the structures will be different. Therefore the above algorithm is no good!

I'm beginning to think that it might be an idea to copy each tree into a linked list and then add the resulting lists, but that is quite wasteful.

[matsp]

How large is this tree [or the range of your indices]?

--
Mats

[Codeplug]

You could just do an in-order traversal of both trees....

Add(Node A, Node B)
{
    Node S;
    
    A = first_inorder(A);
    B = first_inorder(B);

    while (A && B)
    {
        if (A.idx == B.idx)
        {
            insert_node(S, A.idx, A.val + B.val);
        }
        else if (A.idx < B.idx)
        {
            insert_node(S, A.idx, A.val);
            A = next_inorder(A);
        }
        else
        {
            insert_node(S, B.idx, B.val);
            B = next_inorder(B);
        }
    }

    if (A)
        insert_remaining(S, A);
    if (B)
        insert_remaining(S, B);

    return S;
}

The only problem with this is that elements are added to 'S' in an in-order fashion. So unless your tree is self-balancing, you'll end up with a "worst case" tee (a linked list).

gg

[tabstop]

I don't think that a linked-list solution has to be that wasteful. Roughly how many indices will there be? If the answer is "not a whole lot", then maybe some variation on the following idea will work:

For each tree:
1. Traverse the tree.
2. For each node that we visit, look through our linked list for the index of the node.
3a. If we find it, add the value of the current node to the value field of the list.
3b. If we don't, add a new node to the linked list (perhaps even inserting in sorted order of index) with current index and value.

(This assumes the problem is "for each index that appears, add up all the values of nodes with that index, in both trees together", as that's how I'm reading the problem statement.) The answer would have to use that much data anyway (<index, sum> pairs), so I don't see that we've used anything extra.

[iMalc]

That is the problem.. the trees will not have the same indexes in them, and the structures will be different. Therefore the above algorithm is no good!

If they have none of the same indexes in them then how would you know when to add nodes together? I presume you mean that they may share some, but may also have others that are unique in each tree?
Now you perhaps still need to define the output more precisely. Of the nodes that are unique to one of the trees, should these nodes appear in the output?

[willm07]

If they have none of the same indexes in them then how would you know when to add nodes together? I presume you mean that they may share some, but may also have others that are unique in each tree?
Now you perhaps still need to define the output more precisely. Of the nodes that are unique to one of the trees, should these nodes appear in the output?

Sorry, let me clarify.

Each tree may or may not have unique indices.

If an index is unique, then it should appear in the sum.

So basically the sum is an ordered list of unique indices and the sums of non unique ones.

Codeplug, thanks for the code you posted, I have tried it but still no luck. The problem is that you have to recurse backwards on right and left nodes of the tree.

I don't think that a linked-list solution has to be that wasteful. Roughly how many indices will there be? If the answer is "not a whole lot", then maybe some variation on the following idea will work:

For each tree:
1. Traverse the tree.
2. For each node that we visit, look through our linked list for the index of the node.
3a. If we find it, add the value of the current node to the value field of the list.
3b. If we don't, add a new node to the linked list (perhaps even inserting in sorted order of index) with current index and value.

After thinking about this problem for a while and analysing a graph of the different runtimes, I agree with you and so I am going to go with the linked list implementation.

2. For each node that we visit, look through our linked list for the index of the node.

The algorithm I found here:
http://eecs.harvard.edu/~ellard/Q-97...20.html#smmAlg

.. avoids this step by recursing through the lists at the same time.

So the worst case time complexity of each stage will be: (I think..)

1. |a| - convert each tree to a linked list
2. |a| - step through each list, comparing, adding individual elements, and inserting into a new binary tree

Although:

The only problem with this is that elements are added to 'S' in an in-order fashion. So unless your tree is self-balancing, you'll end up with a "worst case" tee (a linked list).

So I might try and add in a function to rebalance the tree afterwards (can't really think of a better solution).

How does that look?

[iMalc]

Okay, I just tried writing this myself and I've determined that it is probably not feasible without modifying the exisiting trees.
I drew two trees with numbers between 1 and 10.
Tree a had 4 as the root and 6 was a leaf node.
Tree b had 6 as the root and 4 was a leaf node.
When you start off you compare the two roots and must search for 6 in tree a, and search for 4 in tree b. That's two log(n) searches. Then you still have to decide which of those becomes the new root, and how the remaining children are linked on.

     4           6
    / \         / \
   /   \       /   \
  2     8     2     8
 / \   / \   / \   / \
1   3 6   9 1   4 7   9

I think it would be doable if you can modify either of the existing tree structures in the process. Then you could treat one of them as a splay tree and say splay a for nodes that you come across in b. For example this would initially bring 6 to the top of tree a, making it a lot easier.

I think it is still better to convert them both to lists.

[Codeplug]

>> I have tried it but still no luck. The problem is that you have to recurse backwards on right and left nodes of the tree.
Who says you *have* to recurse? If you want to avoid copying a entire tree to a list, all you need is a non-recursive in-order traversal - and some balancing code.

gg

[iMalc]

If you really want to you can convert the tree in-place into a list where the left and right pointers are actually prev and next pointers, using the following nifty little code snippet:

template Node *Tree2ListHelper(Node *list, Node *tree) {
	for (;;) {
		if (tree->right) {
			list = Tree2ListHelper(list, tree->right);
			list->left = tree;
		} else if (list)
			list->left = tree;
		tree->right = list;
		if (!tree->left)
			return tree;
		list = tree;
		tree = tree->left;
	}
}

Node *Tree2List(Node *tree) {
	if (!tree)
		return NULL;
	return Tree2ListHelper(NULL, tree);
}

[oogabooga]

I like Codeplug's idea. Can't it be made to work something
like this? (I haven't tested it yet.)

Node stack[ MAXTREEDEPTH ]; /* If you can live with a limit */
int  stackTop = 0;

Node first_inorder( Node N ) {
    while (N->left) {
        stack[ stackTop++ ] = N;
        N = N->left;
    }
    return N;
}

Node next_inorder( Node N ) {
    if (N->right) return first_inorder( N->right );
    return stack[ --stackTop ];
}

If that works then you can get a perfectly balanced tree by Add'ing
into an array of pointers to the new sum nodes. Then construct a
tree by a recursive binary search of the array, but always searching
both ways (instead of always ignoring half), setting the left and right
pointers of each element encountered to the next two elements to
search (or zero), and then recursing on those.

I also like the "nifty little code snippet" posted by iMalc!
If this doesn't work, that will probably do it (and may be best anyway).