BFS, DFS searches required to mark as Visited for trees?

breadth-first-search, depth-first-search, graph, tree

Solution

Your assumption is correct for directed trees.

For undirected trees - if you choose not to mark all visited nodes - you should send an additional variable in the recursion that will tell which neighbor of the current node was already traversed (his parent node in the DFS traverse).

For example DFS in Python (undirected tree):

def dfs(curr_node, parent):
    for node in getNeighbors(curr_node):
        if node!=parent:
            dfs(node)

BFS however, is done iteratively, and you can't avoid marking in the undirected case.

Problem

Looking at the BFS and DFS algorithms they seem to mark the nodes as visited. If I am navigating trees only is it still necessary for my implementation to mark nodes as visited or not? I want to perform some action on every node exactly once. It seems it would be only required for graphs, where cycles exist, creating the possibility that I could bump into the same node twice. If I do the calls recursively for a tree, it does not seem necessary to have a visited status as I can chose to perform the action I want on the node after all the calls from the stack return to the current node. Is my assumption correct? Thanks.

Original source