Trees

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.

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

Basic Implementation

basic.php
Replay: real traced execution (multi-file project)
<?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;
?>

  1. tree ← 4(2(1,3),6(5,7)), queue ← [4]

    1<?php2class Node {
    values this step4(2(1,3),6(5,7))tree[4]queue

  2. output ← [4], queue ← [2, 6]

    18function list_string(array $values): string { return "[" . implode(", ", $values) . "]"; }19$queue = [sample_tree()];20$output = [];
    values this step[4]output[2, 6]queue4dequeued

  3. output ← [4, 2], queue ← [6, 1, 3]

    18function list_string(array $values): string { return "[" . implode(", ", $values) . "]"; }19$queue = [sample_tree()];20$output = [];
    values this step[4, 2]output[6, 1, 3]queue2dequeued

  4. output ← [4, 2, 6], queue ← [1, 3, 5, 7]

    18function list_string(array $values): string { return "[" . implode(", ", $values) . "]"; }19$queue = [sample_tree()];20$output = [];
    values this step[4, 2, 6]output[1, 3, 5, 7]queue6dequeued

  5. output ← [4, 2, 6, 1], queue ← [3, 5, 7]

    18function list_string(array $values): string { return "[" . implode(", ", $values) . "]"; }19$queue = [sample_tree()];20$output = [];
    values this step[4, 2, 6, 1]output[3, 5, 7]queue1dequeued

  6. output ← [4, 2, 6, 1, 3], queue ← [5, 7]

    18function list_string(array $values): string { return "[" . implode(", ", $values) . "]"; }19$queue = [sample_tree()];20$output = [];
    values this step[4, 2, 6, 1, 3]output[5, 7]queue3dequeued

  7. output ← [4, 2, 6, 1, 3, 5], queue ← [7]

    18function list_string(array $values): string { return "[" . implode(", ", $values) . "]"; }19$queue = [sample_tree()];20$output = [];
    values this step[4, 2, 6, 1, 3, 5]output[7]queue5dequeued

  8. output ← [4, 2, 6, 1, 3, 5, 7], queue ← []

    18function list_string(array $values): string { return "[" . implode(", ", $values) . "]"; }19$queue = [sample_tree()];20$output = [];
    values this step[4, 2, 6, 1, 3, 5, 7]output[]queue7dequeued

  9. echo list_string($output) . PHP_EOL;

    21while ($queue) { $node = array_shift($queue); $output[] = $node->value; if ($node->left !== null) $queue[] = $node->left; if ($node->right !== null) $queue[] = $node->right; }22echo list_string($output) . PHP_EOL;23?>
    values this step[4, 2, 6, 1, 3, 5, 7]output

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].