[Tutor] Help to understand tree intersections using hash tables as a collision checker

[Alan Gauld]

On 03/05/2023 17:47, James Ian Solima wrote:

> I thought that I understood how hash tables worked. I was solving this
> algorithm the other day and in that algorithm I am using a hashtable's
> collision check to track if a value occurs twice in two different binary
> trees.

The only hash table type in standard Python is the dictionary(and
maybe set?). But it does not expose methods like collision check
to the user.

But I see you are importing a module called data_structures,
which is not part of the standard library. This list is focused
on the language and standard library so you may not find anyone
who knows about that module. As a minimum tell us where you
found it. PyPI? Github? Part of SciPy?

Or is it a module you have created? In which case we'd need
to see some code.

> input:
> tree1 = 1(2)(3)
> tree2 = 4(2(3)(1))(6(5))
> 
> expected result: [1,2,3]
> 
> My code to solve this was, assume that my Hashtable class has working
> hash(), get(), set(), keys(), has(). And I have a working BinaryTree class
> with working pre_order(), in_order(), and post_order() methods.
> 
> from data_structures.hashtable import Hashtable
> from data_structures.binary_tree.binary_tree import BinaryTree
> def tree_intersection(tree1, tree2):
> # Use hashmap implementation
> hash_table = Hashtable(1024)
> duplicates = set()
> if tree1.root:
> values1 = tree1.pre_order()
> for value in values1:
> hash_table.set(value, value)
> if tree2.root:
> values2 = tree2.pre_order()
> for value in values2:
> if hash_table.has(value) and value not in duplicates:
> duplicates.add(value)
> return list(duplicates)

Without indentation it's almost impossible to be sure what's going
on. Please resend the message using *plain text* rather than HTML
to preserve the layout.

-- 
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.amazon.com/author/alan_gauld
Follow my photo-blog on Flickr at:
http://www.flickr.com/photos/alangauldphotos