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

Question

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.

Answer 1

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.

Answer 2

Your assumption is correct, the marking is needed only with data-structures that have cycles, since trees don't have cycles - you can remove the marking part from your implementation and BFS/DFS should still work!

Example: in-order traverse of a tree is actually running a DFS with an additional "rule" that you always visit the left child first.

Python:

def in-order(node):
    if not node:
        return
    in-order(node.get_left())
    print(node)
    in-order(node.get_right())