Python - Depth-First Search (DFS) for Tree and Graph Traversal

Depth-first search (DFS) is a fundamental algorithm for traversing tree-like or graph-like data structures. It explores as far as possible along a branch before backtracking. You can use it for various tasks, including finding paths, cycle detection, etc. Here's an example:

Example - Depth-First Search in Python for Tree Traversal:

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.children = []

def dfs_tree(node):
    if not node:
        return

    print(node.val)  # Process the current node

    for child in node.children:
        dfs_tree(child)  # Recursively visit child nodes

# Example usage:
root = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)

root.children = [node2, node3]
node2.children = [node4, node5]

dfs_tree(root)  # Traverses and prints the tree nodes in DFS order

We define a basic tree structure using a TreeNode class in this example. We then implement a depth-first search (dfs_tree) to traverse the tree and process nodes in a depth-first manner. DFS is particularly useful for exploring structures like trees, where you want to visit nodes deeply before moving horizontally to sibling nodes.

You can adapt the same DFS concept to traverse graphs by using appropriate data structures (e.g., adjacency lists) and keeping track of visited nodes to avoid infinite loops when dealing with cyclic graphs.