Binary search tree intersection

Question

I have 2 binary search trees T1 and T2 with same number of nodes n >= 1. For each node P we have LEFT(P) and RIGHT(P) for links between nodes and KEY(P) for value off the node. The root of T1 is R1 and root of T2 is R2. I need a linear algorithm which will determine values ​​which are found both in T1 and in T2.

My idea until now is to do an inorder traversal of T1 and search in T2 for current element, like this:

inorder(node)
   if node is not NULL
      inorder(LEFT(node))
      if find(KEY(node), R2)
            print KEY(node)
      inorder(RIGHT(node))

Where find(KEY(node), R2) implement a binary search for KEY(node) in tree T2.

Is this the correct solution? Is this a linear algorithm? (I know traversal is O(n) complexity). Or, there is another method to intersect 2 binary search trees?

Thanks!

Answer 1

Your current inorder traversal using recursion to perform the task. That makes it difficult to run more than one at the same time.

So, first I would re-write the method to use an explicit stack (example here in C#). Now, duplicate all of the state so that we perform traversals of both trees at the same time.

At any point where we're ready to yield a value from both trees, we compare their KEY() values. If they are unequal then we carry on the traversal of the tree with the lower KEY() value.

If both values are equal then we yield that value and continue traversing both trees again.

This is similar in concept to merging two sorted sequences - all we need to do is to examine the "next" value to be yielded by each sequence, yield the lower of the two values and then move forward in that sequence.

---

In answer to your original proposal:

Is this a linear algorithm?

No. For every node you visit during your inorder traversal, you're calling find which is O(log n). So your complete algorithm is (if I remember complexity correctly) O(n log n).