Traversal::preOrderGenerator() - 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

Traversal::preOrderGenerator() A

↳ Parent: Traversal

Complexity

Conditions	4
Paths	5

Size

Total Lines	17
Code Lines	9

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	10
CRAP Score	4

Importance

Changes	1
Bugs	0	Features	0

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

<?php

declare(strict_types=1);

namespace Yoanm\CommonDSA\Algorithm\BinaryTree;

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

/**
 * Binary tree traversal leveraging iterative functions.
 *
 *
 * @see \Yoanm\CommonDSA\Algorithm\BinaryTree\RecursiveTraversal for recursive implementations.
 */
class Traversal
{
    /**
     * @see \Yoanm\CommonDSA\Algorithm\BinaryTree\Traversal::preOrderGenerator()
     *

     *
     * @return 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\BinaryTree\Traversal::inOrderGenerator()
     *
     *
     * @return Node[]
     * @phpstan-return list<Node>
     */
    public static function inOrder(Node $node): array
    {
        // ⚠ Do not preserve keys in order to always return a list !
        return iterator_to_array(self::inOrderGenerator($node), false);
    }

    /**
     * @see \Yoanm\CommonDSA\Algorithm\BinaryTree\Traversal::postOrderGenerator()
     *
     *
     * @return 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\BinaryTree\Traversal::BFSGenerator()
     *
     *
     * @return 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);
    }

    /**
     * @see \Yoanm\CommonDSA\Algorithm\BinaryTree\Traversal::levelOrderGenerator()
     * @see \Yoanm\CommonDSA\Algorithm\BinaryTree\Traversal::BFS() if node level isn't useful.
     *
     *
     * @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);
    }

    /**
     * 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 storing parent nodes path up to the root node.
     *
     *
     * @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;

            if (null !== $currentNode->right) {
                $stack->push($currentNode->right);
            }
            if (null !== $currentNode->left) {
                $stack->push($currentNode->left);
            }
        }
    }

    /**
     * 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 storing parent nodes path up to the root node.
     *
     * @return Generator<Node>
     */
    public static function inOrderGenerator(Node $node): Generator
    {
        /** @var SplStack<Node> $stack */
        $stack = new SplStack();

        $currentNode = $node;
        while (null !== $currentNode || !$stack->isEmpty()) {
            while (null !== $currentNode) {
                $stack->push($currentNode);
                $currentNode = $currentNode->left;
            }

            // Current node becomes the leftmost leaf found
            // (or the same current node in case it doesn't have left node!)
            $currentNode = $stack->pop();

            yield $currentNode;

            // Left is now managed, let's take a look on right side
            $currentNode = $currentNode->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 storing parent nodes path up to the root node.
     *
     *
     * @return Generator<Node>
     */
    public static function postOrderGenerator(Node $node): Generator
    {
        /** @var SplStack<Node> $stack */
        $stack = new SplStack();

        $currentNode = $node;
        while (null !== $currentNode || !$stack->isEmpty()) {
            while (null !== $currentNode) {
                if (null !== $currentNode->right) {
                    $stack->push($currentNode->right);
                }
                $stack->push($currentNode);
                $currentNode = $currentNode->left;
            }

            $currentNode = $stack->pop();

            if (!$stack->isEmpty() && $currentNode->right === $stack->top()) {
                // Remove current node right child from the stack, it will become $currentNode for next iteration
                $stack->pop();

                $stack->push($currentNode);
                $currentNode = $currentNode->right;
            } else {
                yield $currentNode;

                $currentNode = null;
            }
        }
    }

    /**
     * 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 number of nodes for the bigger level
     *
     * TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
     *
     * SC: 𝑂⟮𝑚⟯ - Due to the queue storing current level parent nodes, plus temporary list storing every node
     * for the current level
     *
     *
     *
     * @see \Yoanm\CommonDSA\Algorithm\BinaryTree\Traversal::BFSGenerator() if node level isn't useful.
     *
     *
     * @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;

                if (null !== $node->left) {
                    $queue->enqueue($node->left);
                }
                if (null !== $node->right) {
                    $queue->enqueue($node->right);
                }

                --$currentLevelNodeCounter;
            }

            yield $nodeList;
        }
    }

    /**
     * BFS: Traverse tree level by level, from Left to Right.<br>
     *
     *
     * <br>
     * ### Time/Space complexity
     * With:
     * - 𝑛 the number of node in the tree
     * - 𝑚 the number of nodes for the bigger level
     *
     * TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
     *
     * SC: 𝑂⟮𝑚⟯ - Due to the queue storing current level parent nodes
     *
     *
     * @see \Yoanm\CommonDSA\Algorithm\BinaryTree\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;

                if (null !== $node->left) {
                    $queue->enqueue($node->left);
                }
                if (null !== $node->right) {
                    $queue->enqueue($node->right);
                }

                --$currentLevelNodeCounter;
            }
        }
    }
}


1		<?php
2
3		declare(strict_types=1);
4
5		namespace Yoanm\CommonDSA\Algorithm\BinaryTree;
6
7		use Generator;
8		use SplQueue;
9		use SplStack;
10		use Yoanm\CommonDSA\DataStructure\BinaryTree\NodeInterface as Node;
11
12		/**
13		* Binary tree traversal leveraging iterative functions.
14		*
15		*
16		* @see \Yoanm\CommonDSA\Algorithm\BinaryTree\RecursiveTraversal for recursive implementations.
17		*/
18		class Traversal
19		{
20		/**
21		* @see \Yoanm\CommonDSA\Algorithm\BinaryTree\Traversal::preOrderGenerator()
22		*
23
24		*
25		* @return Node[]
26		* @phpstan-return list<Node>
27		*/
28	7	public static function preOrder(Node $node): array
29		{
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\Traversal::inOrderGenerator()
36		*
37		*
38		* @return Node[]
39		* @phpstan-return list<Node>
40		*/
41	2	public static function inOrder(Node $node): array
42		{
43		// ⚠ Do not preserve keys in order to always return a list !
44	2	return iterator_to_array(self::inOrderGenerator($node), false);
45		}
46
47		/**
48		* @see \Yoanm\CommonDSA\Algorithm\BinaryTree\Traversal::postOrderGenerator()
49		*
50		*
51		* @return Node[]
52		* @phpstan-return list<Node>
53		*/
54	2	public static function postOrder(Node $node): array
55		{
56		// ⚠ Do not preserve keys in order to always return a list !
57	2	return iterator_to_array(self::postOrderGenerator($node), false);
58		}
59
60		/**
61		* @see \Yoanm\CommonDSA\Algorithm\BinaryTree\Traversal::BFSGenerator()
62		*
63		*
64		* @return Node[]
65		* @phpstan-return list<Node>
66		*/
67	3	public static function BFS(Node $node): array
68		{
69		// ⚠ Do not preserve keys in order to always return a list !
70	3	return iterator_to_array(self::BFSGenerator($node), false);
71		}
72
73		/**
74		* @see \Yoanm\CommonDSA\Algorithm\BinaryTree\Traversal::levelOrderGenerator()
75		* @see \Yoanm\CommonDSA\Algorithm\BinaryTree\Traversal::BFS() if node level isn't useful.
76		*
77		*
78		* @return array<int, array<Node>> key is the level, value is the list of nodes for that level
79		* @phpstan-return list<list<Node>>
80		*/
81	3	public static function levelOrder(Node $node): array
82		{
83		// ⚠ Do not preserve keys in order to always return a list !
84	3	return iterator_to_array(self::levelOrderGenerator($node), false);
85		}
86
87		/**
88		* Pre-order: N->L->R => Node, then Left child, then Right child.
89		*
90		*
91		* <br>
92		* ### Time/Space complexity
93		* With:
94		* - 𝑛 the number of node in the tree
95		* - 𝘩 the tree height, usually ㏒(𝑛) (=balanced tree).<br>
96		* ⚠ 𝘩 = 𝑛 if every node has only a left child (skewed tree)
97		*
98		* TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
99		*
100		* SC: 𝑂⟮𝘩⟯ - Due to the stack storing parent nodes path up to the root node.
101		*
102		*
103		* @return Generator<Node>
104		*/
105	14	public static function preOrderGenerator(Node $node): Generator
106		{
107		/** @var SplStack<Node> $stack */
108	14	$stack = new SplStack();
109
110	14	$stack->push($node);
111
112	14	while (!$stack->isEmpty()) {
113	14	$currentNode = $stack->pop();
114
115	14	yield $currentNode;
116
117	14	if (null !== $currentNode->right) {
118	12	$stack->push($currentNode->right);
119		}
120	14	if (null !== $currentNode->left) {
121	12	$stack->push($currentNode->left);
122		}
123		}
124		}
125
126		/**
127		* In-order (=DFS): L->N->R => Left child, then Node, then Right child.
128		*
129		*
130		* <br>
131		* ### Time/Space complexity
132		* With:
133		* - 𝑛 the number of node in the tree
134		* - 𝘩 the tree height, usually ㏒(𝑛) (=balanced tree).<br>
135		* ⚠ 𝘩 = 𝑛 if every node has only a left child (skewed tree)
136		*
137		* TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
138		*
139		* SC: 𝑂⟮𝘩⟯ - Due to the stack storing parent nodes path up to the root node.
140		*
141		* @return Generator<Node>
142		*/
143	4	public static function inOrderGenerator(Node $node): Generator
144		{
145		/** @var SplStack<Node> $stack */
146	4	$stack = new SplStack();
147
148	4	$currentNode = $node;
149	4	while (null !== $currentNode \|\| !$stack->isEmpty()) {
150	4	while (null !== $currentNode) {
151	4	$stack->push($currentNode);
152	4	$currentNode = $currentNode->left;
153		}
154
155		// Current node becomes the leftmost leaf found
156		// (or the same current node in case it doesn't have left node!)
157	4	$currentNode = $stack->pop();
158
159	4	yield $currentNode;
160
161		// Left is now managed, let's take a look on right side
162	4	$currentNode = $currentNode->right;
163		}
164		}
165
166		/**
167		* Post-order: L->R->N => Left child, then Right child, then Node.
168		*
169		*
170		* <br>
171		* ### Time/Space complexity
172		* With:
173		* - 𝑛 the number of node in the tree
174		* - 𝘩 the tree height, usually ㏒(𝑛) (=balanced tree).<br>
175		* ⚠ 𝘩 = 𝑛 if every node has only a left child (skewed tree)
176		*
177		* TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
178		*
179		* SC: 𝑂⟮𝘩⟯ - Due to the stack storing parent nodes path up to the root node.
180		*
181		*
182		* @return Generator<Node>
183		*/
184	4	public static function postOrderGenerator(Node $node): Generator
185		{
186		/** @var SplStack<Node> $stack */
187	4	$stack = new SplStack();
188
189	4	$currentNode = $node;
190	4	while (null !== $currentNode \|\| !$stack->isEmpty()) {
191	4	while (null !== $currentNode) {
192	4	if (null !== $currentNode->right) {
193	4	$stack->push($currentNode->right);
194		}
195	4	$stack->push($currentNode);
196	4	$currentNode = $currentNode->left;
197		}
198
199	4	$currentNode = $stack->pop();
200
201	4	if (!$stack->isEmpty() && $currentNode->right === $stack->top()) {
202		// Remove current node right child from the stack, it will become $currentNode for next iteration
203	4	$stack->pop();
204
205	4	$stack->push($currentNode);
206	4	$currentNode = $currentNode->right;
207		} else {
208	4	yield $currentNode;
209
210	4	$currentNode = null;
211		}
212		}
213		}
214
215		/**
216		* Level order (=BFS): Traverse tree level by level, from Left to Right
217		*
218		*
219		* <br>
220		* 💡 Reverse the list for reversed level-order traversal !
221		* <br>
222		* <br>
223		* ### Time/Space complexity
224		* With:
225		* - 𝑛 the number of node in the tree
226		* - 𝑚 the number of nodes for the bigger level
227		*
228		* TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
229		*
230		* SC: 𝑂⟮𝑚⟯ - Due to the queue storing current level parent nodes, plus temporary list storing every node
231		* for the current level
232		*
233		*
234		*
235		* @see \Yoanm\CommonDSA\Algorithm\BinaryTree\Traversal::BFSGenerator() if node level isn't useful.
236		*
237		*
238		* @return Generator<int, array<Node>> key is the level, value is the list of nodes for that level
239		* @phpstan-return Generator<int, list<Node>>
240		*/
241	6	public static function levelOrderGenerator(Node $node): Generator
242		{
243		/** @var SplQueue<Node> $queue */
244	6	$queue = new SplQueue();
245
246	6	$queue->enqueue($node);
247
248	6	while (!$queue->isEmpty()) {
249	6	$nodeList = [];
250	6	$currentLevelNodeCounter = $queue->count();
251	6	while ($currentLevelNodeCounter > 0) {
252	6	$node = $queue->dequeue();
253
254	6	$nodeList[] = $node;
255
256	6	if (null !== $node->left) {
257	6	$queue->enqueue($node->left);
258		}
259	6	if (null !== $node->right) {
260	6	$queue->enqueue($node->right);
261		}
262
263	6	--$currentLevelNodeCounter;
264		}
265
266	6	yield $nodeList;
267		}
268		}
269
270		/**
271		* BFS: Traverse tree level by level, from Left to Right.<br>
272		*
273		*
274		* <br>
275		* ### Time/Space complexity
276		* With:
277		* - 𝑛 the number of node in the tree
278		* - 𝑚 the number of nodes for the bigger level
279		*
280		* TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
281		*
282		* SC: 𝑂⟮𝑚⟯ - Due to the queue storing current level parent nodes
283		*
284		*
285		* @see \Yoanm\CommonDSA\Algorithm\BinaryTree\Traversal::levelOrderGenerator() if node level must be known !
286		*
287		*
288		* @return Generator<Node>
289		*/
290	6	public static function BFSGenerator(Node $node): Generator
291		{
292		/** @var SplQueue<Node> $queue */
293	6	$queue = new SplQueue();
294
295	6	$queue->enqueue($node);
296	6	while (!$queue->isEmpty()) {
297	6	$currentLevelNodeCounter = $queue->count();
298	6	while ($currentLevelNodeCounter > 0) {
299	6	$node = $queue->dequeue();
300
301	6	yield $node;
302
303	6	if (null !== $node->left) {
304	6	$queue->enqueue($node->left);
305		}
306	6	if (null !== $node->right) {
307	6	$queue->enqueue($node->right);
308		}
309
310	6	--$currentLevelNodeCounter;
311		}
312		}
313		}
314		}
315

yoanm / php-common-dsa

Push — master ( c21857...1d23cf )

Traversal::preOrderGenerator() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like