RecursiveTraversal::levelOrder() - 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

RecursiveTraversal::levelOrder() A

↳ Parent: RecursiveTraversal

Complexity

Conditions	1
Paths	1

Size

Total Lines	11
Code Lines	3

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	4
CRAP Score	1

Importance

Changes	1
Bugs	0	Features	0

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

<?php

declare(strict_types=1);

namespace Yoanm\CommonDSA\Algorithm\NAryTree;

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

/**
 * N-ary tree traversal relying on recursive functions.<br>
 * ⚠ Recursive function implies a growing stack trace, which has a limited size!<br>
 * See {@see \Yoanm\CommonDSA\Algorithm\NAryTree\Traversal} for iterative implementations.
 *
 *
 * @see \Yoanm\CommonDSA\Algorithm\NAryTree\Traversal for iterative implementations.
 */
class RecursiveTraversal
{
    /**
     * @see \Yoanm\CommonDSA\Algorithm\NAryTree\RecursiveTraversal::preOrderGenerator()
     *
     *
     * @return array<Node>
     * @phpstan-return list<Node>
     */
    public static function preOrder(Node $node): array
    {
        // ⚠ Do not preserve keys otherwise there is conflicting keys in case "yield from" is used !
        // ⚠ Do not preserve keys in order to always return a list !
        return iterator_to_array(self::preOrderGenerator($node), false);
    }

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

    /**
     * Level order (=BFS): Traverse tree level by level, 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 list storing every node for every level (see levelOrderHelper() function).
     *
     *
     * @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
    {
        $res = [];

        self::levelOrderHelper($node, $res);

        /**
         * No easy way to tell PHPStan that $res is a list in case level is not provided :/
         * @phpstan-var list<list<Node>> $res
         */
        return $res;
    }

    /**
     * Pre-order: N->Children => Node, then its children (from left to right)
     *
     *
     * <br>
     * ### Time/Space complexity
     * With:
     * - 𝑛 the number of node in the tree
     * - 𝘩 the tree height, usually ㏒(𝑛) (=balanced tree).<br>
     *   ⚠ 𝘩 = 𝑛 if every node has only one child (skewed tree)
     *
     * TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
     *
     * SC: 𝑂⟮𝘩⟯ - Due to the stack trace (recursive calls) + extra space for inner Generator class instances !
     *
     *
     * @return Generator<Node>
     */
    public static function preOrderGenerator(Node $node): Generator
    {
        yield $node;

        foreach ($node->children as $childNode) {
            yield from self::preOrderGenerator($childNode);
        }
    }

    /**
     * Post-order: Children->N => Node **children** (from left to right), then Node
     *
     *
     * <br>
     * ### Time/Space complexity
     * With:
     * - 𝑛 the number of node in the tree
     * - 𝘩 the tree height, usually ㏒(𝑛) (=balanced tree).<br>
     *   ⚠ 𝘩 = 𝑛 if every node has only one child (skewed tree)
     *
     * TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
     *
     * SC: 𝑂⟮𝘩⟯ - Due to the stack trace (recursive calls) + extra space for inner Generator class instances !
     *
     *
     * @return Generator<Node>
     */
    public static function postOrderGenerator(Node $node): Generator
    {
        foreach ($node->children as $childNode) {
            yield from self::postOrderGenerator($childNode);
        }

        yield $node;
    }

    /**
     * Recursive BFS requires to perform a full traversal while keeping the level in memory !
     *
     *
     * <br>
     * ### Time/Space complexity
     * With:
     * - 𝑛 the number of node in the tree
     * - 𝘩 the tree height, usually ㏒(𝑛) (=balanced tree).<br>
     *   ⚠ 𝘩 = 𝑛 if every node has only a left child (skewed tree)
     *
     * TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
     *
     * SC: 𝑂⟮𝘩⟯ - Due to the stack trace (recursive calls)
     *
     *
     * @param array<int, array<Node>> $res key is the level, value is the list of nodes for that level
     * @phpstan-param array<int, list<Node>> $res
     */
    public static function levelOrderHelper(Node $node, array &$res, int $level = 0): void
    {
        $res[$level] ??= []; // In case current level hasn't been seen/managed yet

        $res[$level][] = $node;
        foreach ($node->children as $childNode) {
            self::levelOrderHelper($childNode, $res, $level + 1);
        }
    }
}


1		<?php
2
3		declare(strict_types=1);
4
5		namespace Yoanm\CommonDSA\Algorithm\NAryTree;
6
7		use Generator;
8		use Yoanm\CommonDSA\DataStructure\NAryTree\NodeInterface as Node;
9
10		/**
11		* N-ary tree traversal relying on recursive functions.<br>
12		* ⚠ Recursive function implies a growing stack trace, which has a limited size!<br>
13		* See {@see \Yoanm\CommonDSA\Algorithm\NAryTree\Traversal} for iterative implementations.
14		*
15		*
16		* @see \Yoanm\CommonDSA\Algorithm\NAryTree\Traversal for iterative implementations.
17		*/
18		class RecursiveTraversal
19		{
20		/**
21		* @see \Yoanm\CommonDSA\Algorithm\NAryTree\RecursiveTraversal::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 otherwise there is conflicting keys in case "yield from" is used !
30		// ⚠ Do not preserve keys in order to always return a list !
31	2	return iterator_to_array(self::preOrderGenerator($node), false);
32		}
33
34		/**
35		* @see \Yoanm\CommonDSA\Algorithm\NAryTree\RecursiveTraversal::postOrderGenerator()
36		*
37		*
38		* @return array<Node>
39		* @phpstan-return list<Node>
40		*/
41	2	public static function postOrder(Node $node): array
42		{
43		// ⚠ Do not preserve keys otherwise there is conflicting keys in case "yield from" is used !
44		// ⚠ Do not preserve keys in order to always return a list !
45	2	return iterator_to_array(self::postOrderGenerator($node), false);
46		}
47
48		/**
49		* Level order (=BFS): Traverse tree level by level, from Left to Right
50		*
51		*
52		* <br>
53		* ### Time/Space complexity
54		* With:
55		* - 𝑛 the number of node in the tree
56		*
57		* TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
58		*
59		* SC: 𝑂⟮𝑛⟯ - Due to the list storing every node for every level (see levelOrderHelper() function).
60		*
61		*
62		* @return array<int, array<Node>> key is the level, value is the list of nodes for that level
63		* @phpstan-return list<list<Node>>
64		*/
65	2	public static function levelOrder(Node $node): array
66		{
67	2	$res = [];
68
69	2	self::levelOrderHelper($node, $res);
70
71		/**
72		* No easy way to tell PHPStan that $res is a list in case level is not provided :/
73		* @phpstan-var list<list<Node>> $res
74		*/
75	2	return $res;
76		}
77
78		/**
79		* Pre-order: N->Children => Node, then its children (from left to right)
80		*
81		*
82		* <br>
83		* ### Time/Space complexity
84		* With:
85		* - 𝑛 the number of node in the tree
86		* - 𝘩 the tree height, usually ㏒(𝑛) (=balanced tree).<br>
87		* ⚠ 𝘩 = 𝑛 if every node has only one child (skewed tree)
88		*
89		* TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
90		*
91		* SC: 𝑂⟮𝘩⟯ - Due to the stack trace (recursive calls) + extra space for inner Generator class instances !
92		*
93		*
94		* @return Generator<Node>
95		*/
96	4	public static function preOrderGenerator(Node $node): Generator
97		{
98	4	yield $node;
99
100	4	foreach ($node->children as $childNode) {
101	4	yield from self::preOrderGenerator($childNode);
102		}
103		}
104
105		/**
106		* Post-order: Children->N => Node children (from left to right), then Node
107		*
108		*
109		* <br>
110		* ### Time/Space complexity
111		* With:
112		* - 𝑛 the number of node in the tree
113		* - 𝘩 the tree height, usually ㏒(𝑛) (=balanced tree).<br>
114		* ⚠ 𝘩 = 𝑛 if every node has only one child (skewed tree)
115		*
116		* TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
117		*
118		* SC: 𝑂⟮𝘩⟯ - Due to the stack trace (recursive calls) + extra space for inner Generator class instances !
119		*
120		*
121		* @return Generator<Node>
122		*/
123	4	public static function postOrderGenerator(Node $node): Generator
124		{
125	4	foreach ($node->children as $childNode) {
126	4	yield from self::postOrderGenerator($childNode);
127		}
128
129	4	yield $node;
130		}
131
132		/**
133		* Recursive BFS requires to perform a full traversal while keeping the level in memory !
134		*
135		*
136		* <br>
137		* ### Time/Space complexity
138		* With:
139		* - 𝑛 the number of node in the tree
140		* - 𝘩 the tree height, usually ㏒(𝑛) (=balanced tree).<br>
141		* ⚠ 𝘩 = 𝑛 if every node has only a left child (skewed tree)
142		*
143		* TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
144		*
145		* SC: 𝑂⟮𝘩⟯ - Due to the stack trace (recursive calls)
146		*
147		*
148		* @param array<int, array<Node>> $res key is the level, value is the list of nodes for that level
149		* @phpstan-param array<int, list<Node>> $res
150		*/
151	4	public static function levelOrderHelper(Node $node, array &$res, int $level = 0): void
152		{
153	4	$res[$level] ??= []; // In case current level hasn't been seen/managed yet
154
155	4	$res[$level][] = $node;
156	4	foreach ($node->children as $childNode) {
157	4	self::levelOrderHelper($childNode, $res, $level + 1);
158		}
159		}
160		}
161

yoanm / php-common-dsa

Push — master ( 1d23cf...097598 )

RecursiveTraversal::levelOrder() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like