Level-Order Traversal

Visit a tree breadth-first with a queue.

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this PHP DSA implementation can be compared directly with the rest of the DSA track.

Basic Implementation

basic.php

<?php
class Node {
    public int $value;
    public ?Node $left;
    public ?Node $right;
    public function __construct(int $value, ?Node $left = null, ?Node $right = null) {
        $this->value = $value; $this->left = $left; $this->right = $right;
    }
}
function render_tree(?Node $node): string {
    if ($node === null) return "_";
    if ($node->left === null && $node->right === null) return (string)$node->value;
    return $node->value . "(" . render_tree($node->left) . "," . render_tree($node->right) . ")";
}
function sample_tree(): Node {
    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));
}
function list_string(array $values): string { return "[" . implode(", ", $values) . "]"; }
$queue = [sample_tree()];
$output = [];
while ($queue) { $node = array_shift($queue); $output[] = $node->value; if ($node->left !== null) $queue[] = $node->left; if ($node->right !== null) $queue[] = $node->right; }
echo list_string($output) . PHP_EOL;
?>

Complexity

Time: O(n)
Space: O(w) queue space

Implementation notes

Nodes are PHP objects from class Node with typed int $value and nullable ?Node $left / ?Node $right child links.
sample_tree() creates the checked tree 4(2(1,3),6(5,7)).
$queue = [sample_tree()] stores node objects in a plain PHP array, starting with the root node only.
The loop condition is while ($queue), so traversal stops when the queue array is empty.
$node = array_shift($queue) dequeues the front object; in this small replay, the remaining PHP array slides forward in queue order.
That makes the three-level trace easy to read, but a larger PHP breadth-first traversal would usually keep a head index or use a queue container instead of repeatedly shifting the array front.
$output[] = $node->value records each visited value before children are enqueued.
Child handling is explicit: append $node->left only when it is not null, then append $node->right only when it is not null.
The trace queue/output states are [4], then output [4] with queue [2, 6], then [4, 2] with [6, 1, 3], then [4, 2, 6] with [1, 3, 5, 7].
Leaf dequeues finish the output as [4, 2, 6, 1, 3, 5, 7] and leave the queue empty.
echo list_string($output) . PHP_EOL prints [4, 2, 6, 1, 3, 5, 7].

level order Level-order traversal uses a queue to visit shallower nodes first.