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:
    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):
    return root_node

with unit test:

    # 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:


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:
    return ast

see output:


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?


1 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.


A quick-and-dirty example with generators:

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

def dfs(node):
    stk = [generate_children(node)]

    while stk:
            child = next(stk[-1])
        except StopIteration:
  • \$\begingroup\$ how do you "push generators" or what does that mean? \$\endgroup\$ Commented Jun 29, 2021 at 22:56
  • \$\begingroup\$ For every node you could define a generator, which yields the node's children one by one in order. See edit. \$\endgroup\$
    – vnp
    Commented Jun 29, 2021 at 23:16
  • \$\begingroup\$ FWIW you'd need an iterator, which a generator is a subclass of. You can just replace generate_children(child) with iter(child.children). \$\endgroup\$
    – Peilonrayz
    Commented Jun 30, 2021 at 9:30
  • \$\begingroup\$ @vnp thanks for the comment "stack is last-in-first-out, so the last child pushed will be processed first" that makes sense! I am glad that my reverse sorting is correct + efficient. Perhaps if I had a way to loop backwards without reversing that would be nice. I guess that is what reversed does since it returns an iterator. \$\endgroup\$ Commented Jun 30, 2021 at 17:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.