Day 64: Python Depth-First Search (DFS) on Tree, Stack-Based Iterative Traversal for Deep Exploration Without Recursion

Source: Dev.to

Key Takeaways from Day 64: Iterative DFS Function

1. Function Design: Stack and Visited Initialization

The dfs function takes a tree dictionary and a start node, returning the traversal order:

def dfs(tree: dict, start):
    """Perform DFS traversal starting from the given node."""
    visited = []          # store traversal order
    stack = [start]       # stack for DFS (LIFO)

2. Loop Processing: Pop, Visit, Push Children Reversed

Core while‑loop processes the stack:

    while stack:
        node = stack.pop()               # take the top node from stack

        if node not in visited:
            visited.append(node)         # mark node as visited

            # push children in reverse order to maintain left‑to‑right traversal
            for child in reversed(tree.get(node, [])):
                stack.append(child)

    return visited

• The node is popped and appended to visited if it hasn’t been seen (preorder).
• Children are pushed in reverse order so the leftmost child is processed first.
• tree.get(node, []) safely handles leaf nodes.

3. Example Usage: Defined Tree and Print

Demo with a dictionary‑based tree:

tree = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": [],
    "F": []
}

start_node = "A"

print("Tree:", tree)
print(f"Starting DFS from node: {start_node}")

traversal = dfs(tree, start_node)
print(f"DFS Traversal Order: {traversal}")

Running the script prints the tree, starts DFS from A, and outputs the traversal order [A, B, D, E, C, F]【https://dev.topreorder/】.

Summary and Reflections

• Stack simulates recursion – safe for deep trees.
• Reverse push preserves left‑to‑right order without extra work.
• Visited on pop gives preorder timing.

Recursion is elegant but can fail for depths > 1000. The iterative approach remains safe and controllable.

Next Steps and Resources

• Source Code for Challenge #64: scripts/dfs_tree.py
• Main Repository: 80-days-of-challenges
• Daily Updates: Twitter/X (@Shahrouzlogs)