Tree traversal and merging with Generators

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.

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 and BFS 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, it may help you speed up your work.

dakujem / oliva

Flexible tree structures, materialized path trees, tree iterators.

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 "chains" multiple iterables? 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.

function chained(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).

foreach(chained($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.

foreach(chained(
    [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:

$numbers = chained(
    [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:

$numbers = chained(
    [1,2,3],
    [10 => 4,5],
);
print_r(
    iterator_to_array($numbers)
);

Explore this 3v4l to see the code in action.

The bottomline is this:
We do not use generators for chaining if all we need is to create a merged array, but we may benefit from generators when we need to efficiently iterate over chained arrays or other iterable collections.

By the way, I've written a bit about generators before in Anonymous Generator in PHP.