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

[James Ian Solima]

Hello tutors,

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.

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)

In theory, I expected this to work.

My test code:
import pytest
from code_challenges.tree_intersection.tree_intersection import
tree_intersection
from data_structures.binary_tree.binary_tree import BinaryTree, Node
from data_structures.queue.queue import Queue
def test_exists():
assert tree_intersection
# @pytest.mark.skip("TODO")
def test_tree_intersection():
tree_a = BinaryTree()
values = [150, 100, 250, 75, 160, 200, 350, 125, 175, 300, 500]
add_values_to_empty_tree(tree_a, values)
tree_b = BinaryTree()
values = [42, 100, 100, 15, 160, 200, 350, 125, 175, 4, 500]
add_values_to_empty_tree(tree_b, values)
actual = tree_intersection(tree_a, tree_b)
expected = [125, 175, 100, 160, 500, 200, 350]
print(actual)
assert sorted(actual) == sorted(expected)
def add_values_to_empty_tree(tree, values):
"""
Helper function to add given values to BinaryTree
"""
tree.root = Node(values.pop())
q = Queue()
q.enqueue(tree.root)
while values:
node = q.dequeue()
node.left = Node(values.pop())
node.right = Node(values.pop()) if values else None
q.enqueue(node.left)
q.enqueue(node.right)


This is the actual result that I get when I test the code.

[160, 100, 200, 75, 300, 175, 500, 150, 250, 125, 350]

What I am expecting:

[125, 175, 100, 160, 500, 200, 350]


How and why am I getting the value 75, 250, 150, and all the other numbers
that don't exist in both test trees.

-- 
-James Solima
c. (562) 546-2011
p. (808) 781-9756
Jamesian.R.Solima at gmail.com