"""
Depth first search code for the Recurse Center!
"""

def search_tree(tree, node, target_node):
    """ Finds a node in a tree using depth first search """
    if node == target_node:
        return target_node
    for child_node in tree[node]:
        found_node = search_tree(tree, child_node, target_node)
        if found_node:
            return found_node


if __name__ == '__main__':
    tree = {
      'a': ['b', 'c'],
      'b': ['d', 'e', 'f'],
      'c': ['g'],
      'd': [],
      'e': [],
      'f': [],
      'g': ['h'],
      'h': []
    }

    output = search_tree(tree, 'a', 'g')
    print(output)