leaves.py

from copy import deepcopy
from collections import deque

# Expand a tree to the "leaves"
def leaves_of(item, dependencies):

    # return the leaf nodes
    def dfs2(item, level, visited):
        result = []
        if item in dependencies:
            visited.add(item) # mark that we've seen this branch
            #print(f"{'.'*level}br: {item}")
            for i2 in dependencies[item]:
                if i2 in visited:
                    raise ValueError(f"Circular dependency detected, on item={item}, loops back to {i2}, visited branches={visited}")
                result += dfs2(i2, level+1, deepcopy(visited))
        else:
            #print(f"{'.'*level}leaf:{item}")
            result.append(item) # a leaf node
        return result

    return dfs2(item, 0, set())

#----- NON recursive version
def leaves_of2(item, dependencies):
    stack = deque([(item, set())])
    result = []

    while stack:
        current_item, visited = stack.pop()

        if current_item in dependencies:
            visited.add(current_item)
            for next_item in dependencies[current_item]:
                if next_item in visited:
                    raise ValueError(f"Circular dependency detected, on item={current_item}, loops back to {next_item}, visited branches={visited}")
                stack.append((next_item, visited.copy()))
        else:
            result.append(current_item)
    return result

# Example usage:
items = ['A', 'B', 'C']

dependency_graph = {
    'A': ['B', 'C'],
    'B': ['C'],
    'C': ['D'], # Acceptable
#    'C': ['D', 'A'], # This intentionally shows detection a fatal loop!
}

for item in items:
    try:
        print("Recursion RESULT: ", end='')
        print(item, leaves_of(item, dependency_graph))
    except ValueError as e:
        print(e)
    try:
        print("Deque     RESULT: ", end='')
        print(item, leaves_of2(item, dependency_graph))
    except ValueError as e:
        print(e)