DFS and BFS algorithm in php

1. Problem Setup (Tree Structure)

A generic tree (not binary):

class Node
{
    public function __construct(
        public int $value,
        public array $children = []
    ) {}
}

Tree Visualization

                10
        ┌───────┼────────┬────────┐
        1       2        3        4
        |       |        |     ┌──┴──┐
        5       6        7     8     9

2. BFS (Breadth First Search)

What BFS Means

BFS visits nodes level by level
→ First root
→ Then all children
→ Then grandchildren

Key Data Structure: Queue
Rule: First In → First Out (FIFO)

BFS Algorithm (Concept)

1. Put root node into the queue
2. While queue is not empty:

• Remove the front node
• Process it
• Add all its children to the queue

BFS Code (Your Example, Explained)

$queue = new SplQueue();
$queue->enqueue($root);

while (!$queue->isEmpty()) {

    // Step 1: Take node from front
    $node = $queue->dequeue();

    // Step 2: Process node
    echo $node->value . "<br/>";

    // Step 3: Add children to queue
    foreach ($node->children as $child) {
        $queue->enqueue($child);
    }
}

BFS Execution Order (Step by Step)

BFS Output

10 1 2 3 4 5 6 7 8 9

When to Use BFS

• Level-based traversal
• Shortest path in unweighted graphs
• Tree level order printing

3. DFS (Depth First Search)

What DFS Means

DFS goes as deep as possible before coming back

Key Data Structure: Stack
Rule: Last In → First Out (LIFO)

DFS Algorithm (Iterative)

1. Push root node into stack
2. While stack is not empty:

• Pop top node
• Process it
• Push its children in reverse order

Why reverse?
So left children are processed first (natural order).

DFS Code Using SplStack

$stack = new SplStack();
$stack->push($root);

while (!$stack->isEmpty()) {

    // Step 1: Take top node
    $node = $stack->pop();

    // Step 2: Process node
    echo $node->value . "<br/>";

    // Step 3: Push children (reverse order)
    for ($i = count($node->children) - 1; $i >= 0; $i--) {
        $stack->push($node->children[$i]);
    }
}

DFS Execution Order (Step by Step)

DFS Output

10 1 5 2 6 3 7 4 8 9

When to Use DFS

• Tree recursion replacement
• Path exploration
• Backtracking
• Topological traversal

4. DFS Using Recursion (Classic)

function dfs(Node $node)
{
    echo $node->value . "<br/>";

    foreach ($node->children as $child) {
        dfs($child);
    }
}

dfs($root);

Why Stack Version Is Better in PHP

• No stack overflow for deep trees
• Full control over traversal
• Better for interviews and real systems

5. BFS vs DFS (Quick Comparison)

6. Key Takeaways

• Queue controls BFS
• Stack controls DFS
• Traversal order is defined by data structure behavior
• SPL (SplQueue, SplStack) is standard and efficient