Traverse general tree in level order

level_order_traversal.php

<?php
/**
 * Level order traversal of a general tree.
 *
 * @link https://www.geeksforgeeks.org/generic-tree-level-order-traversal/
 * @package traverse-general-tree
 */

/**
 * Node of an n-ary tree.
 */
class Node {

	/**
	 * Key.
	 *
	 * @var int
	 */
	public $key;

	/**
	 * Child.
	 *
	 * @var array
	 */
	public $child;

	/**
	 * Node constructor.
	 */
	public function __construct() {
		$this->key   = 0;
		$this->child = [];
	}
}

/**
 * Utility function to create a new tree node.
 *
 * @param int $key Key.
 *
 * @return Node
 */
function new_node( $key ) {
	$temp      = new Node();
	$temp->key = $key;

	return $temp;
}

/**
 * Prints the n-ary tree level wise.
 *
 * @param Node $root Root.
 *
 * @return void
 */
function level_order_traversal( $root ) {
	if ( null === $root ) {
		return;
	}

	// Standard level order traversal code using queue.
	$q   = []; // Create a queue.
	$q[] = $root; // Push root.
	$n   = count( $q );

	while ( 0 !== $n ) {
		// If this node has children.
		while ( $n > 0 ) {
			// Dequeue an item from queue and print it.
			$p = $q[0];
			array_shift( $q );
			echo( $p->key . ' ' );

			// Push all children of the dequeued item.
			foreach ( $p->child as $value ) {
				$q[] = $value;
			}

			$n--;
		}

		$n = count( $q );

		// Print new line between two levels.
		echo( "\n" );
	}
}

/**
 * Driver code.
 * Let us create the below tree.
 *       10
 *    / / \ \
 *   2 34 56 100
 *  / \   | / | \
 * 77 88  1 7 8 9
 */
$root                    = new_node( 10 );
$root->child[]           = new_node( 2 );
$root->child[]           = new_node( 34 );
$root->child[]           = new_node( 56 );
$root->child[]           = new_node( 100 );
$root->child[0]->child[] = new_node( 77 );
$root->child[0]->child[] = new_node( 88 );
$root->child[2]->child[] = new_node( 1 );
$root->child[3]->child[] = new_node( 7 );
$root->child[3]->child[] = new_node( 8 );
$root->child[3]->child[] = new_node( 9 );

echo( "Level Order Traversal Before Mirroring\n" );
level_order_traversal( $root );

// Expected result.
/**
 * Level Order Traversal Before Mirroring
 * 10
 * 2 34 56 100
 * 77 88 1 7 8 9
 */