flatten an adjecent list depth first in two ways

from collections import (
    OrderedDict,
    deque,
)

g = OrderedDict()

g["root"] = ["a", "b", "c"]

g["a"] = ["e","f","g"]

g["e"] = []
g["f"] = ["w"]
g["g"] = []
g["w"] = []

g["b"] = ["d"]
g["d"] = ["j"]
g["j"] = []

g["c"] = ["h", "i"]

g["h"] = ["x"]
g["i"] = []
g["x"] = []


# Reference post:
# https://www.educative.io/edpresso/how-to-implement-depth-first-search-in-python
# strategy recursion.
def flatten_graph2(node_id, graph):
    """
    Given a node_id and graph (or tree),
    return a list of every descendant node_id, depth first.
    """

    flat_graph = []

    def dfs(node, graph):
        flat_graph.append(node)
        for child in graph[node]:
            dfs(child, graph)

    dfs(node_id, graph)

    return flat_graph


# Reference post:
# http://kmkeen.com/python-trees/2010-09-18-08-55-50-039.html
# strategy queue.
def flatten_graph(node_id, graph):
    """
    Given a node_id and graph (or tree),
    return a list of every descendant node_id, depth first.
    """

    flat_graph = []

    to_crawl = deque([node_id])

    while to_crawl:
        current_id = to_crawl.pop()

        flat_graph.append(current_id)

        children_ids = graph[current_id]

        # reverse so that we extend the queue in the expected order.
        children_ids.reverse()

        to_crawl.extend(children_ids)

    return flat_graph


flat_graph = flatten_graph2("root", g)
print(flat_graph)

flat_graph = flatten_graph("root", g)
print(flat_graph)