Skip to content

Instantly share code, notes, and snippets.

@kagg-design
Last active January 22, 2023 09:20
Show Gist options
  • Save kagg-design/f04ef5bbd421dac502285f6f4f9933cd to your computer and use it in GitHub Desktop.
Save kagg-design/f04ef5bbd421dac502285f6f4f9933cd to your computer and use it in GitHub Desktop.
Traverse general tree in level order
<?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
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment