RecursiveTraversal::levelOrder() - Code Metrics - Inspection of "Add binary tree traversal, data-structure and fact..." - yoanm/php-common-dsa - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — master ( c21857...1d23cf )

by Yo

created 2025-10-22 16:58 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\BinaryTree;

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

/**
 * Binary 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\BinaryTree\Traversal} for iterative implementations.
 *
 *
 * @see \Yoanm\CommonDSA\Algorithm\BinaryTree\Traversal for iterative implementations.
 */
class RecursiveTraversal
{
    /**
     * @see \Yoanm\CommonDSA\Algorithm\BinaryTree\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\BinaryTree\RecursiveTraversal::preOrderGenerator()
     *
     *
     * @return array<Node>
     * @phpstan-return list<Node>
     */
    public static function inOrder(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::inOrderGenerator($node), false);
    }

    /**
     * @see \Yoanm\CommonDSA\Algorithm\BinaryTree\RecursiveTraversal::inOrderGenerator()
     *
     *
     * @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>
     * 💡 Reverse the list for reversed level-order traversal !
     * <br>
     * <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->L->R => Node, then Left child, then Right child
     *
     * <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) + extra space for inner Generator class instances !
     *
     *
     * @return Generator<Node>
     */
    public static function preOrderGenerator(Node $node): Generator
    {
        yield $node;

        if (null !== $node->left) {
            yield from self::preOrderGenerator($node->left);
        }
        if (null !== $node->right) {
            yield from self::preOrderGenerator($node->right);
        }
    }

    /**
     * In-order (=DFS): L->N->R => Left child, then Node, then Right child
     *
     * <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) + extra space for inner Generator class instances !
     *
     *
     * @return Generator<Node>
     */
    public static function inOrderGenerator(Node $node): Generator
    {
        if (null !== $node->left) {
            yield from self::inOrderGenerator($node->left);
        }

        yield $node;

        if (null !== $node->right) {
            yield from self::inOrderGenerator($node->right);
        }
    }

    /**
     * Post-order: L->R->N => Left child, then Right child, 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 a left 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
    {
        if (null !== $node->left) {
            yield from self::postOrderGenerator($node->left);
        }
        if (null !== $node->right) {
            yield from self::postOrderGenerator($node->right);
        }
        yield $node;
    }

    /**
     * Level order (=BFS): Traverse tree level by level, from Left to Right
     *
     *
     * <br>
     * 💡 Reverse the list for reversed level-order traversal !
     * <br>
     * <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: 𝑂⟮h⟯ - 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;
        if (null !== $node->left) {
            self::levelOrderHelper($node->left, $res, $level + 1);
        }
        if (null !== $node->right) {
            self::levelOrderHelper($node->right, $res, $level + 1);
        }
    }
}


1		<?php
2
3		declare(strict_types=1);
4
5		namespace Yoanm\CommonDSA\Algorithm\BinaryTree;
6
7		use Generator;
8		use Yoanm\CommonDSA\DataStructure\BinaryTree\NodeInterface as Node;
9
10		/**
11		* Binary 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\BinaryTree\Traversal} for iterative implementations.
14		*
15		*
16		* @see \Yoanm\CommonDSA\Algorithm\BinaryTree\Traversal for iterative implementations.
17		*/
18		class RecursiveTraversal
19		{
20		/**
21		* @see \Yoanm\CommonDSA\Algorithm\BinaryTree\RecursiveTraversal::preOrderGenerator()
22		*
23		*
24		* @return array<Node>
25		* @phpstan-return list<Node>
26		*/
27	7	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	7	return iterator_to_array(self::preOrderGenerator($node), false);
32		}
33
34		/**
35		* @see \Yoanm\CommonDSA\Algorithm\BinaryTree\RecursiveTraversal::preOrderGenerator()
36		*
37		*
38		* @return array<Node>
39		* @phpstan-return list<Node>
40		*/
41	2	public static function inOrder(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::inOrderGenerator($node), false);
46		}
47
48		/**
49		* @see \Yoanm\CommonDSA\Algorithm\BinaryTree\RecursiveTraversal::inOrderGenerator()
50		*
51		*
52		* @return array<Node>
53		* @phpstan-return list<Node>
54		*/
55	2	public static function postOrder(Node $node): array
56		{
57		// ⚠ Do not preserve keys otherwise there is conflicting keys in case "yield from" is used !
58		// ⚠ Do not preserve keys in order to always return a list !
59	2	return iterator_to_array(self::postOrderGenerator($node), false);
60		}
61
62		/**
63		* Level order (=BFS): Traverse tree level by level, from Left to Right
64		*
65		*
66		* <br>
67		* 💡 Reverse the list for reversed level-order traversal !
68		* <br>
69		* <br>
70		* ### Time/Space complexity
71		* With:
72		* - 𝑛 the number of node in the tree
73		*
74		* TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
75		*
76		* SC: 𝑂⟮𝑛⟯ - Due to the list storing every node for every level (see levelOrderHelper() function).
77		*
78		*
79		* @return array<int, array<Node>> key is the level, value is the list of nodes for that level
80		* @phpstan-return list<list<Node>>
81		*/
82	3	public static function levelOrder(Node $node): array
83		{
84	3	$res = [];
85
86	3	self::levelOrderHelper($node, $res);
87
88		/**
89		* No easy way to tell PHPStan that $res is a list in case level is not provided :/
90		* @phpstan-var list<list<Node>> $res
91		*/
92	3	return $res;
93		}
94
95		/**
96		* Pre-order: N->L->R => Node, then Left child, then Right child
97		*
98		* <br>
99		* ### Time/Space complexity
100		* With:
101		* - 𝑛 the number of node in the tree
102		* - 𝘩 the tree height, usually ㏒(𝑛) (=balanced tree).<br>
103		* ⚠ 𝘩 = 𝑛 if every node has only a left child (skewed tree)
104		*
105		* TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
106		*
107		* SC: 𝑂⟮𝘩⟯ - Due to the stack trace (recursive calls) + extra space for inner Generator class instances !
108		*
109		*
110		* @return Generator<Node>
111		*/
112	14	public static function preOrderGenerator(Node $node): Generator
113		{
114	14	yield $node;
115
116	14	if (null !== $node->left) {
117	12	yield from self::preOrderGenerator($node->left);
118		}
119	14	if (null !== $node->right) {
120	12	yield from self::preOrderGenerator($node->right);
121		}
122		}
123
124		/**
125		* In-order (=DFS): L->N->R => Left child, then Node, then Right child
126		*
127		* <br>
128		* ### Time/Space complexity
129		* With:
130		* - 𝑛 the number of node in the tree
131		* - 𝘩 the tree height, usually ㏒(𝑛) (=balanced tree).<br>
132		* ⚠ 𝘩 = 𝑛 if every node has only a left child (skewed tree)
133		*
134		* TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
135		*
136		* SC: 𝑂⟮𝘩⟯ - Due to the stack trace (recursive calls) + extra space for inner Generator class instances !
137		*
138		*
139		* @return Generator<Node>
140		*/
141	4	public static function inOrderGenerator(Node $node): Generator
142		{
143	4	if (null !== $node->left) {
144	4	yield from self::inOrderGenerator($node->left);
145		}
146
147	4	yield $node;
148
149	4	if (null !== $node->right) {
150	4	yield from self::inOrderGenerator($node->right);
151		}
152		}
153
154		/**
155		* Post-order: L->R->N => Left child, then Right child, then Node
156		*
157		* <br>
158		* ### Time/Space complexity
159		* With:
160		* - 𝑛 the number of node in the tree
161		* - 𝘩 the tree height, usually ㏒(𝑛) (=balanced tree).<br>
162		* ⚠ 𝘩 = 𝑛 if every node has only a left child (skewed tree)
163		*
164		* TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
165		*
166		* SC: 𝑂⟮𝘩⟯ - Due to the stack trace (recursive calls) + extra space for inner Generator class instances !
167		*
168		*
169		* @return Generator<Node>
170		*/
171	4	public static function postOrderGenerator(Node $node): Generator
172		{
173	4	if (null !== $node->left) {
174	4	yield from self::postOrderGenerator($node->left);
175		}
176	4	if (null !== $node->right) {
177	4	yield from self::postOrderGenerator($node->right);
178		}
179	4	yield $node;
180		}
181
182		/**
183		* Level order (=BFS): Traverse tree level by level, from Left to Right
184		*
185		*
186		* <br>
187		* 💡 Reverse the list for reversed level-order traversal !
188		* <br>
189		* <br>
190		* ### Time/Space complexity
191		* With:
192		* - 𝑛 the number of node in the tree
193		* - 𝘩 the tree height, usually ㏒(𝑛) (=balanced tree).<br>
194		* ⚠ 𝘩 = 𝑛 if every node has only a left child (skewed tree)
195		*
196		* TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
197		*
198		* SC: 𝑂⟮h⟯ - Due to the stack trace (recursive calls)
199		*
200		*
201		* @param array<int, array<Node>> $res key is the level, value is the list of nodes for that level
202		* @phpstan-param array<int, list<Node>> $res
203		*/
204	6	public static function levelOrderHelper(Node $node, array &$res, int $level = 0): void
205		{
206	6	$res[$level] ??= []; // In case current level hasn't been seen/managed yet
207
208	6	$res[$level][] = $node;
209	6	if (null !== $node->left) {
210	6	self::levelOrderHelper($node->left, $res, $level + 1);
211		}
212	6	if (null !== $node->right) {
213	6	self::levelOrderHelper($node->right, $res, $level + 1);
214		}
215		}
216		}
217

yoanm / php-common-dsa

Push — master ( c21857...1d23cf )

RecursiveTraversal::levelOrder() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like