How does one write DFS in python with a Deque without reversed for Trees?

Question

I have implemented a correct version of DFS (with comments explaining the implementation):

from lark import Lark, tree, Tree, Token

def dfs(root_node : Tree, f) -> Tree:
    """

    To do DFS we need to implement a stack. In other words we need to go down the depth until the depth has been
    fully processed. In other words what you want is the the current child you are adding to the dequeue to be processed
    first i.e. you want it to skip the line. To do that you can append to the front of the queue (with append_left and
    then pop_left i.e. pop from that same side).
    :param root_node:
    :param f:
    :return:
    """
    dq = deque([root_node])
    while len(dq) != 0:
        current_node = dq.popleft()  # to make sure you pop from the front since you are adding at the front.
        current_node.data = f(current_node.data)
        # print(current_node.children)
        for child in reversed(current_node.children):
            dq.appendleft(child)
    return root_node

with unit test:

    print()
    # token requires two values due to how Lark works, ignore it
    ast = Tree(1, [Tree(2, [Tree(3, []), Tree(4, [])]), Tree(5, [])])
    # the key is that 3,4 should go first than 5 because it is DFS
    dfs(ast, print)

the output is as I expected it:

1
2
3
4
5

however, it looks rather strange to have a reversed in the code (plus it looks inefficient unless the list is implemented with a head and tail pointer list). How does one change this code so that it looks like the standard "append to the end and pop from the same end". Doing that blindly however for trees leads to wrong printing:

def dfs_stack(ast : Tree, f) -> Tree:
    stack = [ast]
    while len(stack) != 0:
        current_node = stack.pop()  # pop from the end, from the side you are adding
        current_node.data = f(current_node.data)
        for child in current_node.children:
            stack.append(child)
    return ast

see output:

1
5
2
4
3

note my second implementation is based on Depth First Search Using Stack in Python which is for graphs. Perhaps the reason I need to reverse it is because I am traversing a tree where the children ordering matters but the children ordering does not matter in a graph and it makes that code look cleaner (so there is no clear way of how to add for a graph but the invariant of "traversing the children before the siblings" is respected just not in the order I'd expect for trees).

Is there a way to remove the reversed so that the code is still correct and it looks more similar to the standard DFS?

Answer 1

Doing that blindly however for trees leads to wrong printing

No surprise here. In the initial version the deque functions like a stack, so when you change it to the honest-to-goodness stack nothing changes: you still need to push children nodes in the reverse order (stack is last-in-first-out, so the last child pushed will be processed first).

There are few options avoid reversal.

• A plain old recursion.

• If the goal is to not recurse, don't push a list of children. Push generators instead.

Edit:

A quick-and-dirty example with generators:

def generate_children(node):
    for child in node.children:
        yield child

def dfs(node):
    print(node.data)
    stk = [generate_children(node)]

    while stk:
        try:
            child = next(stk[-1])
            print(child.data)
            stk.append(generate_children(child))
        except StopIteration:
            stk.pop()