<?php
namespace DataStructures\AVLTree;
abstract class TreeTraversal
{
public static function inOrder(?AVLTreeNode $node): array
{
$result = [];
if ($node !== null) {
$result = array_merge($result, self::inOrder($node->left));
$result[] = [$node->key => $node->value];
$result = array_merge($result, self::inOrder($node->right));
}
return $result;
}
public static function preOrder(?AVLTreeNode $node): array
{
$result = [];
if ($node !== null) {
$result[] = [$node->key => $node->value];
$result = array_merge($result, self::preOrder($node->left));
$result = array_merge($result, self::preOrder($node->right));
}
return $result;
}
public static function postOrder(?AVLTreeNode $node): array
{
$result = [];
if ($node !== null) {
$result = array_merge($result, self::postOrder($node->left));
$result = array_merge($result, self::postOrder($node->right));
$result[] = [$node->key => $node->value];
}
return $result;
}
public static function breadthFirst(?AVLTreeNode $root): array
{
$result = [];
if ($root === null) {
return $result;
}
$queue = [];
$queue[] = $root;
while (!empty($queue)) {
$currentNode = array_shift($queue);
$result[] = [$currentNode->key => $currentNode->value];
if ($currentNode->left !== null) {
$queue[] = $currentNode->left;
}
if ($currentNode->right !== null) {
$queue[] = $currentNode->right;
}
}
return $result;
}
}