ReversedTraversal::BFSGenerator() - 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

ReversedTraversal::BFSGenerator() A

↳ Parent: ReversedTraversal

Complexity

Conditions	5
Paths	6

Size

Total Lines	21
Code Lines	12

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	13
CRAP Score	5

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	5
eloc	12
c	1
b	0
f	0
nc	6
nop	1
dl	0
loc	21
ccs	13
cts	13
cp	1
crap	5
rs	9.5555

<?php

declare(strict_types=1);

namespace Yoanm\CommonDSA\Algorithm\BinaryTree;

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

/**
 * Reversed binary tree traversal leveraging iterative functions.
 *
 *
 * <br>
 * ℹ Reversed level-order is not implemented as it implies to keep track of and look at each and every node in
 * order to detect the last level => Time and space complexity will be 𝑂⟮𝑛⟯ in any cases !<br>
 * Workaround:<br>
 * 1. Fetch the result of {@see \Yoanm\CommonDSA\Algorithm\BinaryTree\Traversal::levelOrder}
 *    or {@see \Yoanm\CommonDSA\Algorithm\BinaryTree\Traversal::levelOrderGenerator}
 * 2. Either start from the end or reverse the whole list (the latter implies
 *    an additional 𝑂⟮𝑛⟯ time complexity though !)
 *
 *
 * @see \Yoanm\CommonDSA\Algorithm\BinaryTree\RecursiveReversedTraversal for recursive implementations.
 */
class ReversedTraversal
{
    /**
     * @see \Yoanm\CommonDSA\Algorithm\BinaryTree\RevervedTraversal::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\BinaryTree\RevervedTraversal::inOrderGenerator()
     *
     *
     * @return array<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\RevervedTraversal::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\BinaryTree\RevervedTraversal::BFSGenerator()
     *
     *
     * @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);
    }

    /**
     * Reversed Pre-order: N->R->L => Node, then Right children, then Left children
     *
     *
     * <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 right 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->left) {
                $stack->push($currentNode->left);
            }
            if (null !== $currentNode->right) {
                $stack->push($currentNode->right);
            }
        }
    }

    /**
     * Reversed In-order (=Reversed DFS): R->N->L => Right children, then Node, then Left children
     *
     *
     * <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 right 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->right;
            }

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

            yield $currentNode;

            // Right is now managed, let's take a look on left side
            $currentNode = $currentNode->left;
        }
    }

    /**
     * Reversed Post-order: R->L->N => Right children, then Left children, 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 right child (skewed tree)
     *
     * TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
     *
     * SC: 𝑂⟮𝘩⟯ - Due to the stack storing parent nodes.
     *
     *
     * @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->left) {
                    $stack->push($currentNode->left);
                }
                $stack->push($currentNode);
                $currentNode = $currentNode->right;
            }

            $currentNode = $stack->pop();

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

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

                $currentNode = null;
            }
        }
    }

    /**
     * Reversed BFS: Traverse tree level by level, from Right to Left.<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
     *
     *
     * @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->right) {
                    $queue->enqueue($node->right);
                }
                if (null !== $node->left) {
                    $queue->enqueue($node->left);
                }

                --$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		* Reversed binary tree traversal leveraging iterative functions.
14		*
15		*
16		* <br>
17		* ℹ Reversed level-order is not implemented as it implies to keep track of and look at each and every node in
18		* order to detect the last level => Time and space complexity will be 𝑂⟮𝑛⟯ in any cases !<br>
19		* Workaround:<br>
20		* 1. Fetch the result of {@see \Yoanm\CommonDSA\Algorithm\BinaryTree\Traversal::levelOrder}
21		* or {@see \Yoanm\CommonDSA\Algorithm\BinaryTree\Traversal::levelOrderGenerator}
22		* 2. Either start from the end or reverse the whole list (the latter implies
23		* an additional 𝑂⟮𝑛⟯ time complexity though !)
24		*
25		*
26		* @see \Yoanm\CommonDSA\Algorithm\BinaryTree\RecursiveReversedTraversal for recursive implementations.
27		*/
28		class ReversedTraversal
29		{
30		/**
31		* @see \Yoanm\CommonDSA\Algorithm\BinaryTree\RevervedTraversal::preOrderGenerator()
32		*
33		*
34		* @return array<Node>
35		* @phpstan-return list<Node>
36		*/
37	2	public static function preOrder(Node $node): array
38		{
39		// ⚠ Do not preserve keys in order to always return a list !
40	2	return iterator_to_array(self::preOrderGenerator($node), false);
41		}
42
43		/**
44		* @see \Yoanm\CommonDSA\Algorithm\BinaryTree\RevervedTraversal::inOrderGenerator()
45		*
46		*
47		* @return array<Node>
48		* @phpstan-return list<Node>
49		*/
50	2	public static function inOrder(Node $node): array
51		{
52		// ⚠ Do not preserve keys in order to always return a list !
53	2	return iterator_to_array(self::inOrderGenerator($node), false);
54		}
55
56		/**
57		* @see \Yoanm\CommonDSA\Algorithm\BinaryTree\RevervedTraversal::postOrderGenerator()
58		*
59		*
60		* @return array<Node>
61		* @phpstan-return list<Node>
62		*/
63	2	public static function postOrder(Node $node): array
64		{
65		// ⚠ Do not preserve keys in order to always return a list !
66	2	return iterator_to_array(self::postOrderGenerator($node), false);
67		}
68
69		/**
70		* @see \Yoanm\CommonDSA\Algorithm\BinaryTree\RevervedTraversal::BFSGenerator()
71		*
72		*
73		* @return array<Node>
74		* @phpstan-return list<Node>
75		*/
76	3	public static function BFS(Node $node): array
77		{
78		// ⚠ Do not preserve keys in order to always return a list !
79	3	return iterator_to_array(self::BFSGenerator($node), false);
80		}
81
82		/**
83		* Reversed Pre-order: N->R->L => Node, then Right children, then Left children
84		*
85		*
86		* <br>
87		* ### Time/Space complexity
88		* With:
89		* - 𝑛 the number of node in the tree
90		* - 𝘩 the tree height, usually ㏒(𝑛) (=balanced tree).<br>
91		* ⚠ 𝘩 = 𝑛 if every node has only a right child (skewed tree)
92		*
93		* TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
94		*
95		* SC: 𝑂⟮𝘩⟯ - Due to the stack storing parent nodes path up to the root node.
96		*
97		*
98		* @return Generator<Node>
99		*/
100	4	public static function preOrderGenerator(Node $node): Generator
101		{
102		/** @var SplStack<Node> $stack */
103	4	$stack = new SplStack();
104
105	4	$stack->push($node);
106	4	while (!$stack->isEmpty()) {
107	4	$currentNode = $stack->pop();
108
109	4	yield $currentNode;
110
111	4	if (null !== $currentNode->left) {
112	4	$stack->push($currentNode->left);
113		}
114	4	if (null !== $currentNode->right) {
115	4	$stack->push($currentNode->right);
116		}
117		}
118		}
119
120		/**
121		* Reversed In-order (=Reversed DFS): R->N->L => Right children, then Node, then Left children
122		*
123		*
124		* <br>
125		* ### Time/Space complexity
126		* With:
127		* - 𝑛 the number of node in the tree
128		* - 𝘩 the tree height, usually ㏒(𝑛) (=balanced tree).<br>
129		* ⚠ 𝘩 = 𝑛 if every node has only a right child (skewed tree)
130		*
131		* TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
132		*
133		* SC: 𝑂⟮𝘩⟯ - Due to the stack storing parent nodes path up to the root node.
134		*
135		*
136		* @return Generator<Node>
137		*/
138	4	public static function inOrderGenerator(Node $node): Generator
139		{
140		/** @var SplStack<Node> $stack */
141	4	$stack = new SplStack();
142
143	4	$currentNode = $node;
144	4	while (null !== $currentNode \|\| !$stack->isEmpty()) {
145	4	while (null !== $currentNode) {
146	4	$stack->push($currentNode);
147	4	$currentNode = $currentNode->right;
148		}
149
150		// Current node becomes the rightmost leaf found
151		// (or the same current node in case it doesn't have right node!)
152	4	$currentNode = $stack->pop();
153
154	4	yield $currentNode;
155
156		// Right is now managed, let's take a look on left side
157	4	$currentNode = $currentNode->left;
158		}
159		}
160
161		/**
162		* Reversed Post-order: R->L->N => Right children, then Left children, then Node
163		*
164		*
165		* <br>
166		* ### Time/Space complexity
167		* With:
168		* - 𝑛 the number of node in the tree
169		* - 𝘩 the tree height, usually ㏒(𝑛) (=balanced tree).<br>
170		* ⚠ 𝘩 = 𝑛 if every node has only a right child (skewed tree)
171		*
172		* TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
173		*
174		* SC: 𝑂⟮𝘩⟯ - Due to the stack storing parent nodes.
175		*
176		*
177		* @return Generator<Node>
178		*/
179	4	public static function postOrderGenerator(Node $node): Generator
180		{
181		/** @var SplStack<Node> $stack */
182	4	$stack = new SplStack();
183
184	4	$currentNode = $node;
185	4	while (null !== $currentNode \|\| !$stack->isEmpty()) {
186	4	while (null !== $currentNode) {
187	4	if (null !== $currentNode->left) {
188	4	$stack->push($currentNode->left);
189		}
190	4	$stack->push($currentNode);
191	4	$currentNode = $currentNode->right;
192		}
193
194	4	$currentNode = $stack->pop();
195
196	4	if (!$stack->isEmpty() && $currentNode->left === $stack->top()) {
197		// Remove current node left child from the stack, it will become $currentNode for next iteration
198	4	$stack->pop();
199
200	4	$stack->push($currentNode);
201	4	$currentNode = $currentNode->left;
202		} else {
203	4	yield $currentNode;
204
205	4	$currentNode = null;
206		}
207		}
208		}
209
210		/**
211		* Reversed BFS: Traverse tree level by level, from Right to Left.<br>
212		*
213		*
214		* <br>
215		* ### Time/Space complexity
216		* With:
217		* - 𝑛 the number of node in the tree
218		* - 𝑚 the number of nodes for the bigger level
219		*
220		* TC: 𝑂⟮𝑛⟯ - Each node will be visited only one time
221		*
222		* SC: 𝑂⟮𝑚⟯ - Due to the queue storing current level parent nodes
223		*
224		*
225		* @return Generator<Node>
226		*/
227	6	public static function BFSGenerator(Node $node): Generator
228		{
229		/** @var SplQueue<Node> $queue */
230	6	$queue = new SplQueue();
231
232	6	$queue->enqueue($node);
233	6	while (!$queue->isEmpty()) {
234	6	$currentLevelNodeCounter = $queue->count();
235	6	while ($currentLevelNodeCounter > 0) {
236	6	$node = $queue->dequeue();
237
238	6	yield $node;
239
240	6	if (null !== $node->right) {
241	6	$queue->enqueue($node->right);
242		}
243	6	if (null !== $node->left) {
244	6	$queue->enqueue($node->left);
245		}
246
247	6	--$currentLevelNodeCounter;
248		}
249		}
250		}
251		}
252

yoanm / php-common-dsa

Push — master ( c21857...1d23cf )

ReversedTraversal::BFSGenerator() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like