def breadthFirstSearch(problem):
    """Search the shallowest nodes in the search tree first."""
    "*** YOUR CODE HERE ***"
    visited = set()
    directions = util.Queue()
    queue = util.Queue()
    visited.add(problem.getStartState())
    for node in problem.getSuccessors(problem.getStartState()):
        queue.push(node[0])
        directions.push([node[1]])
        visited.add(node[0])


    successor = queue.pop()
    path = directions.pop()
    while not problem.isGoalState(successor):

        for node in problem.getSuccessors(successor):

            if node[0] not in visited:
                queue.push(node[0])
                directions.push(path + [node[1]])
                visited.add(node[0])

        successor = queue.pop()
        path = directions.pop()
    return path