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
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?