DEV Community

Shahrouz Nikseresht
Shahrouz Nikseresht

Posted on

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

#challenge #python #datastructures #algorithms

Welcome to Day 64 of the #80DaysOfChallenges journey! This intermediate challenge implements Depth-First Search (DFS) on a tree structure using an iterative stack approach, avoiding recursion to prevent stack overflow on deep trees while achieving the same "go deep first" behavior. It uses a dict for adjacency, a list as stack for LIFO, and visited tracking for order, making it perfect for tree/graph traversal without the risks of recursive calls. If you're mastering non-recursive algorithms, preparing for interview questions like tree traversals (preorder DFS), or building search in hierarchical data, this "Python iterative DFS" script is safe, efficient, and the exact method used in production when recursion depth is a concern.

💡 Key Takeaways from Day 64: Iterative DFS Function

This task features a function that simulates recursion with a stack, pushing children in reverse for left-to-right order. It's a stack-based DFS pattern: pop, visit, push children. We'll detail: function with stack and visited list, loop for pop and child push, and example tree with print.

1. Function Design: Stack and Visited Initialization

The dfs function takes tree dict and start node, returns 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)
Enter fullscreen mode Exit fullscreen mode

Visited list records order, stack starts with root for LIFO deep dive.

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

Core while processes 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
Enter fullscreen mode Exit fullscreen mode

Pop node, append to visited if new (preorder). Push children reversed so leftmost pops first (left-to-right). tree.get(node, []) handles leaves. For tree A->B,C; B->D,E: order A,B,D,E,C,F.

3. Example Usage: Defined Tree and Print

Demo with dict 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}")
Enter fullscreen mode Exit fullscreen mode

Prints tree, runs DFS from A, shows A, B, D, E, C, F.

🎯 Summary and Reflections

This iterative DFS replaces recursion with stack for safety and control. It reinforced:

  • Stack simulates recursion: Perfect for deep trees.
  • Reverse push for order: Left-to-right without extra work.
  • Visited on pop: Preorder timing.

Reflections: Recursion elegant but risky for depth >1000. Iterative always safe.

Advanced Alternatives: Recursive DFS. Postorder/inorder variants. Graph with visited set. Your traversal tip? Share!

🚀 Next Steps and Resources

Day 64 conquered non-recursive DFS. In #80DaysOfChallenges? Tried graphs? Post!

Top comments (0)