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)

Queue State	Current Node	Output
[10]	10	10
[1,2,3,4]	1	1
[2,3,4,5]	2	2
[3,4,5,6]	3	3
[4,5,6,7]	4	4
[5,6,7,8,9]	5	5
[6,7,8,9]	6	6
[7,8,9]	7	7
[8,9]	8	8
[9]	9	9

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)

Stack State	Current Node	Output
[10]	10	10
[4,3,2,1]	1	1
[4,3,2,5]	5	5
[4,3,2]	2	2
[4,3,6]	6	6
[4,3]	3	3
[4,7]	7	7
[4]	4	4
[9,8]	8	8
[9]	9	9

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)

Feature	BFS	DFS
Data Structure	Queue	Stack
Traversal	Level by level	Deep first
Memory	Higher	Lower
Shortest Path	Yes	No
Implementation	Iterative	Recursive or Iterative

---

6. Key Takeaways

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