You seem to make use often return 1
. It would be better to use booleans to show a clear intention of what you wnat to return.
Also, your hash_route
, which you build as a dict
, has a constant value that is never used, making it effectively a set
, which is fine if all you care is the lowest common ancestor.
I would go for:
def traverse_DFS(root, target_node_value, ancestor_set):
# print('looking at node ' + str(root.value))
if root.value == target_node_value:
# print('found node ' + str(target_node_value))
ancestor_set.add(root.value)
return True
else:
if root.left_child:
left_result = traverse_DFS(root.left_child, target_node_value,
ancestor_set)
if left_result:
ancestor_set.add(root.value)
return True
if root.right_child:
right_result = traverse_DFS(root.right_child, target_node_value,
ancestor_set)
if right_result:
ancestor_set.add(root.value)
return True
return False
I would also get rid of common_ancestor
global variable (avoid them whenever you can, and also when you think you cannot, since you most probably can anyway). You can easily carry that information in the return value, together with the flag for the found node.
def hash_find_ancestor_DFS(root, target_node_value, ancestor_set):
if root.value == target_node_value:
if root.value in ancestor_set:
return (True, root.value)
else:
return (True, None)
else:
if root.left_child:
(found, ancestor) = hash_find_ancestor_DFS(root.left_child, target_node_value,
ancestor_set)
if found:
if ancestor:
return (True, ancestor)
elif root.value in ancestor_set:
return (True, root.value)
else:
return (True, None)
if root.right_child:
(found, ancestor) = hash_find_ancestor_DFS(root.right_child, target_node_value,
ancestor_set)
if found:
if ancestor:
return (True, ancestor)
elif root.value in ancestor_set:
return (True, root.value)
else:
return (True, None)
return (False, None)
For completeness, this would be the other function:
def find_common_node(Tree, node1, node2):
print('Running the common ancestry finder')
# First run DFS v1 with Hash
hash_route= set()
print('This value of node1 is ' + str(node1))
found = traverse_DFS(Tree.root, node1, hash_route)
if not found:
return None
print(hash_route)
(found, common_ancestor) = hash_find_ancestor_DFS(Tree.root, node2, hash_route)
return common_ancestor
I added a check to shortcut the second search if the node is not found in the first.