2

I have two BSTs consist of elements with unique ids. I want to find the common elements of these BSTs.

The simplest way is to get the elements of the first BST one by one and check them against the second BST. But since I have to repeat this comparison zillions times, I am looking for the fastest algorithm.

viegets
  • 119
  • 1
  • 7

2 Answers2

2

Say your two trees are of size m and n, respectively. Your proposed solution works in time Θ(n log(m)) (or the other way around). You can actually do this in time Θ(m + n).

Let's start with a related problem. Suppose you have two lists, each of them sorted, of size m and n respectively. You can easily find the number of common elements in Θ(m + n). Simply place two "pointers", one per list. by comparing the two items, you can figure out if to increment the first pointer, the second one, or both (the last case being when identical elements were found). (Edit - you can see this in the answer to this question.)

In-order traversal of a BST is conceptually the same as traversal of a sorted linked list, so you can do the same here.

Community
  • 1
  • 1
Ami Tavory
  • 74,578
  • 11
  • 141
  • 185
  • Interesting, Actually it helps me a lot. Thanks. However the idea I'm looking for is something like [Bloom filter](https://en.wikipedia.org/wiki/Bloom_filter) in BSTs. I think at the end, it would be better for me to replace all the AVL trees with simple sorted arrays and use the algorithm you mentioned. Because the way I implemented my BST and inorder traversal makes it really hard for me to use this algorithm. – viegets Dec 02 '16 at 12:13
1

You could do a traversal (pre-, in-, or post-order) of one BST and store the value of the nodes in a hash table. Then do a traversal of the other tree and increment the corresponding value in the hash table for each node encountered. Any value in the hash table with a value greater than 1 is a value that is in common with both binary search trees.

J. Michael Wuerth
  • 272
  • 1
  • 6