Traversal::BFS() - Code Metrics - Inspection of "Add N-ary tree traversal, data-structure and facto..." - yoanm/php-common-dsa - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — master ( 1d23cf...097598 )

by Yo

created 2025-10-22 17:26 UTC

Traversal::BFS() A

↳ Parent: Traversal

Complexity

Conditions	1
Paths	1

Size

Total Lines	4
Code Lines	1

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	2
CRAP Score	1

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	1
eloc	1
c	1
b	0
f	0
nc	1
nop	1
dl	0
loc	4
ccs	2
cts	2
cp	1
crap	1
rs	10

<?php

declare(strict_types=1);

namespace Yoanm\CommonDSA\Algorithm\NAryTree;

use Generator;
use SplQueue;
use SplStack;
use Yoanm\CommonDSA\DataStructure\NAryTree\NodeInterface as Node;

/**
 * N-ary tree traversal leveraging iterative functions.
 *
 *
 * @see \Yoanm\CommonDSA\Algorithm\NAryTree\RecursiveTraversal for recursive implementations.
 */
class Traversal
{
    /**
     * @see \Yoanm\CommonDSA\Algorithm\NAryTree\Traversal::preOrderGenerator()
     *
     *
     * @return array<Node>
     * @phpstan-return list<Node>
     */
    public static function preOrder(Node $node): array
    {
        // ⚠ Do not preserve keys in order to always return a list !
        return iterator_to_array(self::preOrderGenerator($node), false);
    }

    /**
     * @see \Yoanm\CommonDSA\Algorithm\NAryTree\Traversal::postOrderGenerator()
     *
     *
     * @return array<Node>
     * @phpstan-return list<Node>
     */
    public static function postOrder(Node $node): array
    {
        // ⚠ Do not preserve keys in order to always return a list !
        return iterator_to_array(self::postOrderGenerator($node), false);
    }

    /**
     * @see \Yoanm\CommonDSA\Algorithm\NAryTree\Traversal::levelOrderGenerator()
     *
     *
     * @return array<int, array<Node>> key is the level, value is the list of nodes for that level
     * @phpstan-return list<list<Node>>
     */
    public static function levelOrder(Node $node): array
    {
        // ⚠ Do not preserve keys in order to always return a list !
        return iterator_to_array(self::levelOrderGenerator($node), false);
    }

    /**
     * @see \Yoanm\CommonDSA\Algorithm\NAryTree\Traversal::BFSGenerator()
     * @see \Yoanm\CommonDSA\Algorithm\NAryTree\Traversal::levelOrder() if node level must be known !
     *
     *
     * @return array<Node>
     * @phpstan-return list<Node>
     */
    public static function BFS(Node $node): array
    {
        // ⚠ Do not preserve keys in order to always return a list !
        return iterator_to_array(self::BFSGenerator($node), false);
    }

    /**
     * Pre-order: N->Children => Node, then its children (from left to right)
     *
     *
     * <br>
     * ### Time/Space complexity
     * With:
     * - 𝑛 the number of node in the tree
     *
     * TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
     *
     * SC: 𝑂⟮𝑛⟯ - Due to the stack storing parent nodes
     *            + worse scenario like when every level first node has a lot of children.<br>
     *            𝑂⟮𝟷⟯ for best scenario where each node has only one child (skewed tree)!
     *
     *            => Worse case example: Tree with 3 levels
     *            - level 1 has 1 node (root node) with 4 children
     *            - level 2 first node has 10 children
     *
     *            ==> 𝑛 = 15 (1 + 4 + 10)
     *
     *            1. before 1st iteration => stack size = 1 (the root node)
     *            2. 1st iteration, first node of level 1 (root node) is removed,
     *               its 4 children added => stack size = (1 - 1) + 4 = 4
     *            3. 2nd iteration, first node of level 2 is removed, its 10 children added
     *               => stack size = (4 - 1) + 10 = 13
     *
     *            ==> stack size = 13 at the beginning of 3rd iteration.
     *            13 is not exactly 𝑛 but Complexity calculation doesn't take into account nodes already removed
     *            which leads to almost 𝑛
     *
     *
     * @return Generator<Node>
     */
    public static function preOrderGenerator(Node $node): Generator
    {
        /** @var SplStack<Node> $stack */
        $stack = new SplStack();
        $stack->push($node);

        while (!$stack->isEmpty()) {
            $currentNode = $stack->pop();

            yield $currentNode;

            // Start from the end of the list as we use a Stack (Last In First Out) !!
            $childNode = end($currentNode->children);
            while (false !== $childNode) {
                $stack->push($childNode);
                $childNode = prev($currentNode->children);
            }
        }
    }

    /**
     * Post-order: Children->N => Node **children** (from left to right), then Node
     *
     *
     * <br>
     * ### Time/Space complexity
     * With:
     * - 𝑛 the number of node in the tree
     *
     * TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
     *
     * SC: 𝑂⟮𝑛⟯ - Due to the stack storing parent nodes
     *            + worse scenario like when every level first node has a lot of children.<br>
     *            𝑂⟮㏒ 𝑛⟯ for best scenario where each node has only one child (skewed tree) !
     *
     *            => Worse case example: Tree with 3 levels
     *            - level 1 has 1 node (root node) with 4 children
     *            - level 2 first node has 10 children
     *
     *            ==> 𝑛 = 15 (1 + 4 + 10)
     *
     *            1. before 1st iteration => stack size = 1 (the root node)
     *            2. 1st iteration, children from first node of level 1 (root node) are added
     *               -> 4 children added => stack size = 1 + 4 = 5
     *            3. 2nd iteration, children from first node of level 2 are added
     *               -> 10 children added => stack size = 5 + 10 = 15
     *
     *            ==> stack size = 15 at the beginning of 3rd iteration.
     *
     *
     * @return Generator<Node>
     */
    public static function postOrderGenerator(Node $node): Generator
    {
        /** @var SplStack<Node> $stack */
        $stack = new SplStack();
        $stack->push($node);

        /** @var Node|null $lastManagedNode */
        $lastManagedNode = null;
        while (!$stack->isEmpty()) {
            $node = $stack->top();

            $currentNodeChildCount = count($node->children);
            // Process current node only in specific cases:
            if (
                // No children to process (=nothing to process before current node)
                0 === $currentNodeChildCount
                // last managed node is the last child of the current node
                // (=nothing **more** to process before current node)
                || $lastManagedNode === $node->children[$currentNodeChildCount - 1]
            ) {
                yield $node;
                $stack->pop(); // Remove current node from the stack
                $lastManagedNode = $node; // Set current node as the last one managed
            } else { // Otherwise, push current node children and keep current node in the stack
                // Start from the end of the list as we use a Stack (Last In First Out) !!
                $childNode = end($node->children);
                while (false !== $childNode) {
                    $stack->push($childNode);
                    $childNode = prev($node->children);
                }
            }
        }
    }

    /**
     * Level order (=BFS): Traverse tree level by level, from Left to Right
     *
     *
     * <br>
     * ### Time/Space complexity
     * With:
     * - 𝑛 the number of node in the tree
     * - 𝑚 the number of nodes for the bigger level.<br>
     *   ⚠ 𝑚 = (𝑛 − 1) if there is only two levels, root + children
     *
     * TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
     *
     * SC: 𝑂⟮𝑚⟯ - Due to the temporary list storing every node for the current level.
     *
     *
     * @return Generator<int, array<Node>> key is the level, value is the list of nodes for that level
     * @phpstan-return Generator<int, list<Node>>
     */
    public static function levelOrderGenerator(Node $node): Generator
    {
        /** @var SplQueue<Node> $queue */
        $queue = new SplQueue();
        $queue->enqueue($node);

        while (!$queue->isEmpty()) {
            $nodeList = [];
            $currentLevelNodeCounter = $queue->count();
            while ($currentLevelNodeCounter > 0) {
                $node = $queue->dequeue();

                $nodeList[] = $node;

                foreach ($node->children as $childNode) {
                    $queue->enqueue($childNode);
                }

                --$currentLevelNodeCounter;
            }

            yield $nodeList;
        }
    }

    /**
     * BFS: Traverse tree level by level, from Left to Right
     *
     *
     * <br>
     * ### Time/Space complexity
     * With:
     * - 𝑛 the number of node in the tree
     * - 𝑚 the number of nodes for the bigger level.<br>
     *   ⚠ 𝑚 = (𝑛 − 1) if there is only two levels, root + children
     *
     * TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
     *
     * SC: 𝑂⟮𝑚⟯ - Due to the queue storing current level parent nodes
     *
     *
     * @see \Yoanm\CommonDSA\Algorithm\NAryTree\Traversal::levelOrderGenerator() if node level must be known !
     *
     *
     * @return Generator<Node>
     */
    public static function BFSGenerator(Node $node): Generator
    {
        /** @var SplQueue<Node> $queue */
        $queue = new SplQueue();
        $queue->enqueue($node);

        while (!$queue->isEmpty()) {
            $currentLevelNodeCounter = $queue->count();
            while ($currentLevelNodeCounter > 0) {
                $node = $queue->dequeue();

                yield $node;

                foreach ($node->children as $childNode) {
                    $queue->enqueue($childNode);
                }

                --$currentLevelNodeCounter;
            }
        }
    }
}


1		<?php
2
3		declare(strict_types=1);
4
5		namespace Yoanm\CommonDSA\Algorithm\NAryTree;
6
7		use Generator;
8		use SplQueue;
9		use SplStack;
10		use Yoanm\CommonDSA\DataStructure\NAryTree\NodeInterface as Node;
11
12		/**
13		* N-ary tree traversal leveraging iterative functions.
14		*
15		*
16		* @see \Yoanm\CommonDSA\Algorithm\NAryTree\RecursiveTraversal for recursive implementations.
17		*/
18		class Traversal
19		{
20		/**
21		* @see \Yoanm\CommonDSA\Algorithm\NAryTree\Traversal::preOrderGenerator()
22		*
23		*
24		* @return array<Node>
25		* @phpstan-return list<Node>
26		*/
27	2	public static function preOrder(Node $node): array
28		{
29		// ⚠ Do not preserve keys in order to always return a list !
30	2	return iterator_to_array(self::preOrderGenerator($node), false);
31		}
32
33		/**
34		* @see \Yoanm\CommonDSA\Algorithm\NAryTree\Traversal::postOrderGenerator()
35		*
36		*
37		* @return array<Node>
38		* @phpstan-return list<Node>
39		*/
40	2	public static function postOrder(Node $node): array
41		{
42		// ⚠ Do not preserve keys in order to always return a list !
43	2	return iterator_to_array(self::postOrderGenerator($node), false);
44		}
45
46		/**
47		* @see \Yoanm\CommonDSA\Algorithm\NAryTree\Traversal::levelOrderGenerator()
48		*
49		*
50		* @return array<int, array<Node>> key is the level, value is the list of nodes for that level
51		* @phpstan-return list<list<Node>>
52		*/
53	2	public static function levelOrder(Node $node): array
54		{
55		// ⚠ Do not preserve keys in order to always return a list !
56	2	return iterator_to_array(self::levelOrderGenerator($node), false);
57		}
58
59		/**
60		* @see \Yoanm\CommonDSA\Algorithm\NAryTree\Traversal::BFSGenerator()
61		* @see \Yoanm\CommonDSA\Algorithm\NAryTree\Traversal::levelOrder() if node level must be known !
62		*
63		*
64		* @return array<Node>
65		* @phpstan-return list<Node>
66		*/
67	2	public static function BFS(Node $node): array
68		{
69		// ⚠ Do not preserve keys in order to always return a list !
70	2	return iterator_to_array(self::BFSGenerator($node), false);
71		}
72
73		/**
74		* Pre-order: N->Children => Node, then its children (from left to right)
75		*
76		*
77		* <br>
78		* ### Time/Space complexity
79		* With:
80		* - 𝑛 the number of node in the tree
81		*
82		* TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
83		*
84		* SC: 𝑂⟮𝑛⟯ - Due to the stack storing parent nodes
85		* + worse scenario like when every level first node has a lot of children.<br>
86		* 𝑂⟮𝟷⟯ for best scenario where each node has only one child (skewed tree)!
87		*
88		* => Worse case example: Tree with 3 levels
89		* - level 1 has 1 node (root node) with 4 children
90		* - level 2 first node has 10 children
91		*
92		* ==> 𝑛 = 15 (1 + 4 + 10)
93		*
94		* 1. before 1st iteration => stack size = 1 (the root node)
95		* 2. 1st iteration, first node of level 1 (root node) is removed,
96		* its 4 children added => stack size = (1 - 1) + 4 = 4
97		* 3. 2nd iteration, first node of level 2 is removed, its 10 children added
98		* => stack size = (4 - 1) + 10 = 13
99		*
100		* ==> stack size = 13 at the beginning of 3rd iteration.
101		* 13 is not exactly 𝑛 but Complexity calculation doesn't take into account nodes already removed
102		* which leads to almost 𝑛
103		*
104		*
105		* @return Generator<Node>
106		*/
107	4	public static function preOrderGenerator(Node $node): Generator
108		{
109		/** @var SplStack<Node> $stack */
110	4	$stack = new SplStack();
111	4	$stack->push($node);
112
113	4	while (!$stack->isEmpty()) {
114	4	$currentNode = $stack->pop();
115
116	4	yield $currentNode;
117
118		// Start from the end of the list as we use a Stack (Last In First Out) !!
119	4	$childNode = end($currentNode->children);
120	4	while (false !== $childNode) {
121	4	$stack->push($childNode);
122	4	$childNode = prev($currentNode->children);
123		}
124		}
125		}
126
127		/**
128		* Post-order: Children->N => Node children (from left to right), then Node
129		*
130		*
131		* <br>
132		* ### Time/Space complexity
133		* With:
134		* - 𝑛 the number of node in the tree
135		*
136		* TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
137		*
138		* SC: 𝑂⟮𝑛⟯ - Due to the stack storing parent nodes
139		* + worse scenario like when every level first node has a lot of children.<br>
140		* 𝑂⟮㏒ 𝑛⟯ for best scenario where each node has only one child (skewed tree) !
141		*
142		* => Worse case example: Tree with 3 levels
143		* - level 1 has 1 node (root node) with 4 children
144		* - level 2 first node has 10 children
145		*
146		* ==> 𝑛 = 15 (1 + 4 + 10)
147		*
148		* 1. before 1st iteration => stack size = 1 (the root node)
149		* 2. 1st iteration, children from first node of level 1 (root node) are added
150		* -> 4 children added => stack size = 1 + 4 = 5
151		* 3. 2nd iteration, children from first node of level 2 are added
152		* -> 10 children added => stack size = 5 + 10 = 15
153		*
154		* ==> stack size = 15 at the beginning of 3rd iteration.
155		*
156		*
157		* @return Generator<Node>
158		*/
159	4	public static function postOrderGenerator(Node $node): Generator
160		{
161		/** @var SplStack<Node> $stack */
162	4	$stack = new SplStack();
163	4	$stack->push($node);
164
165		/** @var Node\|null $lastManagedNode */
166	4	$lastManagedNode = null;
167	4	while (!$stack->isEmpty()) {
168	4	$node = $stack->top();
169
170	4	$currentNodeChildCount = count($node->children);
171		// Process current node only in specific cases:
172		if (
173		// No children to process (=nothing to process before current node)
174	4	0 === $currentNodeChildCount
175		// last managed node is the last child of the current node
176		// (=nothing more to process before current node)
177	4	\|\| $lastManagedNode === $node->children[$currentNodeChildCount - 1]
178		) {
179	4	yield $node;
180	4	$stack->pop(); // Remove current node from the stack
181	4	$lastManagedNode = $node; // Set current node as the last one managed
182		} else { // Otherwise, push current node children and keep current node in the stack
183		// Start from the end of the list as we use a Stack (Last In First Out) !!
184	4	$childNode = end($node->children);
185	4	while (false !== $childNode) {
186	4	$stack->push($childNode);
187	4	$childNode = prev($node->children);
188		}
189		}
190		}
191		}
192
193		/**
194		* Level order (=BFS): Traverse tree level by level, from Left to Right
195		*
196		*
197		* <br>
198		* ### Time/Space complexity
199		* With:
200		* - 𝑛 the number of node in the tree
201		* - 𝑚 the number of nodes for the bigger level.<br>
202		* ⚠ 𝑚 = (𝑛 − 1) if there is only two levels, root + children
203		*
204		* TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
205		*
206		* SC: 𝑂⟮𝑚⟯ - Due to the temporary list storing every node for the current level.
207		*
208		*
209		* @return Generator<int, array<Node>> key is the level, value is the list of nodes for that level
210		* @phpstan-return Generator<int, list<Node>>
211		*/
212	4	public static function levelOrderGenerator(Node $node): Generator
213		{
214		/** @var SplQueue<Node> $queue */
215	4	$queue = new SplQueue();
216	4	$queue->enqueue($node);
217
218	4	while (!$queue->isEmpty()) {
219	4	$nodeList = [];
220	4	$currentLevelNodeCounter = $queue->count();
221	4	while ($currentLevelNodeCounter > 0) {
222	4	$node = $queue->dequeue();
223
224	4	$nodeList[] = $node;
225
226	4	foreach ($node->children as $childNode) {
227	4	$queue->enqueue($childNode);
228		}
229
230	4	--$currentLevelNodeCounter;
231		}
232
233	4	yield $nodeList;
234		}
235		}
236
237		/**
238		* BFS: Traverse tree level by level, from Left to Right
239		*
240		*
241		* <br>
242		* ### Time/Space complexity
243		* With:
244		* - 𝑛 the number of node in the tree
245		* - 𝑚 the number of nodes for the bigger level.<br>
246		* ⚠ 𝑚 = (𝑛 − 1) if there is only two levels, root + children
247		*
248		* TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
249		*
250		* SC: 𝑂⟮𝑚⟯ - Due to the queue storing current level parent nodes
251		*
252		*
253		* @see \Yoanm\CommonDSA\Algorithm\NAryTree\Traversal::levelOrderGenerator() if node level must be known !
254		*
255		*
256		* @return Generator<Node>
257		*/
258	4	public static function BFSGenerator(Node $node): Generator
259		{
260		/** @var SplQueue<Node> $queue */
261	4	$queue = new SplQueue();
262	4	$queue->enqueue($node);
263
264	4	while (!$queue->isEmpty()) {
265	4	$currentLevelNodeCounter = $queue->count();
266	4	while ($currentLevelNodeCounter > 0) {
267	4	$node = $queue->dequeue();
268
269	4	yield $node;
270
271	4	foreach ($node->children as $childNode) {
272	4	$queue->enqueue($childNode);
273		}
274
275	4	--$currentLevelNodeCounter;
276		}
277		}
278		}
279		}
280

yoanm / php-common-dsa

Push — master ( 1d23cf...097598 )

Traversal::BFS() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like