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?