Skip to main content
Fixed a little typo
Source Link
Toby Speight
  • 81.7k
  • 14
  • 101
  • 308

You seem to make use often return 1. It would be better to use booleans to show a clear intention of what you wnatwant to return.

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.

You seem to make use often return 1. It would be better to use booleans to show a clear intention of what you want to return.

Source Link
bracco23
  • 384
  • 1
  • 4

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.