Tree traversal and merging with Generators
Tags: php, code
Published: 2024-02-11 16:01:32

## Tree traversal 

Recently I reimplemented my old library for tree structure handling.

It turns out that **generators** along with **recursion** are a very efficient and concise way to traverse tree structures.

Below, the two depth-first traversals (pre-order, post-order) are implemented by 3 lines of code, and the breadth-first level-order traversal by 5.

```php
final class Traversal
{
    public static function preOrder(TreeNodeContract $node): Generator
    {
        // First, yield the current node,
        // then do the same for all the children.
        yield $node;
        foreach ($node->children() as $child) {
            yield from self::preOrder($child);
        }
    }

    public static function postOrder(TreeNodeContract $node): Generator
    {
        // Yield the current node last,
        // after recursively calling this for all it's children.
        foreach ($node->children() as $child) {
            yield from self::postOrder($child);
        }
        yield $node;
    }

    public static function levelOrder(TreeNodeContract $node): Generator
    {
        // In BFS traversal a queue has to be used instead of recursion.
        $queue = [$node];

        // The first node in the queue is taken and yielded,
        // then all of its children are added to the queue.
        // The next iterations will continue with the node's children, while adding their children to the queue,
        // until there are no more nodes to traverse.
        while ($node = array_shift($queue)) {
            yield $node;
            foreach ($node->children() as $child) {
                $queue[] = $child;
            }
        }
    }
}
```

> 💡
>
> You can tell a generator by the `yield` keyword. In fact, every method or function that `yield` appears in automatically returns a generator. A generator is a special type of single-use iterator. In simple terms, it is best used with `foreach`.

Wikipedia will tell you more about [DFS](https://en.wikipedia.org/wiki/Depth-first_search) and [BFS](https://en.wikipedia.org/wiki/Breadth-first_search) tree traversals.
Try to compare the code complexity using stacks to implement the same.

If you are interested in tree structures in PHP, see the library [`dakujem/oliva`](https://github.com/dakujem/oliva), it may help you speed up your work.

{% github dakujem/oliva no-readme %}


## Generators for merging arrays and iterators

In my opinion, **generators** are one of the lesser known and underrated features of PHP, albeit with narrow field of use, but very useful in some specific cases.

See how this simple function "merges" multiple `iterable`s? That means any arrays or iterators in one bag.
And it's **efficient**, it does not actually merge anything, it merely enables iteration over every element of whatever the input is.
```php
function merged(iterable ...$input): Generator
{
    foreach ($input as $iterable) {
        yield from $iterable;
    }
}
```

From now on, if you need to iterate over multiple arrays, no need to use `array_merge` (which would merge the arrays, increasing memory usage and possibly slowing down the code).

```php
foreach(merged($array1, $array2, $array3) as $key => $value){
    // ...
}
```

However, take care that the keys may overlap - a single key may appear multiple times for different values and is thus not unique. That would be problematic if you used `iterator_to_array`.

```php
foreach(merged(
    [1,2,3],
    [4,5],
) as $item){
    echo "$item ";
}
```
The above results in the expected sequence of numbers `1 2 3 4 5 ` being printed.
However, the below code does not print what's naturally expected:
```php
$numbers = merged(
    [1,2,3],
    [4,5],
);
print_r(iterator_to_array($numbers));
```
The output is 
```
Array
(
    [0] => 4
    [1] => 5
    [2] => 3
)
```

This is because the indexes in the input arrays overlap and are overwritten when calling `iterator_to_array`.

This one works as expected again, as there are no overlapping indexes:
```php
$numbers = merged(
    [1,2,3],
    [10 => 4,5],
);
print_r(
    iterator_to_array($numbers)
);
```

Explore [this 3v4l](https://3v4l.org/D7spa) to see the code in action.

The bottomline is this:
We do not use generators for merging if we need to create an array, but we may benefit from generators when we need to efficiently iterate over seemingly merged arrays or other iterables.


> By the way, I've written a bit about generators before in [Anonymous Generator in PHP](https://dev.to/dakujem/anonymous-generator-in-php-4nn1).