How can i find the max depth

Question

How can i make a FindMaxDepth method / This function will find the longest depth of the tree (the distance between the root node and the last leaf node), the input that the function will take is: (graph, rootNode) and the output will be a numeric value.

Example: If the following graph is entered and the startNode = A, the output must be 4

graph = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": ["F"],
    "F": [],
}
visited = []


def dfs(visited, graph, root):
    if root not in visited:
        visited.append(root)
        print(root)
        for child in graph[root]:
            dfs(visited, graph, child)


dfs(visited, graph, "A")


def bfs(graph, root):
    visited = []
    queue = []
    visited.append(root)
    queue.append(root)
    while queue:
        x = queue.pop(0)
        print(x)
        for child in graph[x]:
            if child not in visited:
                visited.append(child)
                queue.append(child)


# bfs(graph, "A")

Answer 1

bfs can track this internally, since it isn't recursive. dfs needs a global (or simulated global) to track the maximum.

graph = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": ["F"],
    "F": [],
}
visited = []


def dfs(visited, graph, root, depth=0):
    global maxdepth
    maxdepth = max(depth,maxdepth)
    if root not in visited:
        visited.append(root)
        print(root)
        for child in graph[root]:
            dfs(visited, graph, child, depth+1)


maxdepth = 0
dfs(visited, graph, "A")
print("max depth", maxdepth)


def bfs(graph, root):
    maxdepth = 0
    visited = []
    queue = []
    visited.append(root)
    queue.append((root,1))
    while queue:
        x,depth = queue.pop(0)
        maxdepth = max(maxdepth,depth)
        print(x)
        for child in graph[x]:
            if child not in visited:
                visited.append(child)
                queue.append((child,depth+1))
    return maxdepth

print("max depth", bfs(graph, "A"))