Trees

Preorder Traversal

Visit the root before each subtree, producing root-left-right order.

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.

preorder Preorder records the current node before visiting left and right subtrees.

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) . "]"; }
function preorder(?Node $node, array &$output): void { if ($node === null) return; $output[] = $node->value; preorder($node->left, $output); preorder($node->right, $output); }
$output = [];
preorder(sample_tree(), $output);
echo list_string($output) . PHP_EOL;
?>

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

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

  2. output ← [4]

    18function list_string(array $values): string { return "[" . implode(", ", $values) . "]"; }19function preorder(?Node $node, array &$output): void { if ($node === null) return; $output[] = $node->value; preorder($node->left, $output); preorder($node->right, $output); }20$output = [];
    values this step[] → [4]output4node

  3. output ← [4, 2]

    18function list_string(array $values): string { return "[" . implode(", ", $values) . "]"; }19function preorder(?Node $node, array &$output): void { if ($node === null) return; $output[] = $node->value; preorder($node->left, $output); preorder($node->right, $output); }20$output = [];
    values this step[4] → [4, 2]output2node

  4. output ← [4, 2, 1]

    18function list_string(array $values): string { return "[" . implode(", ", $values) . "]"; }19function preorder(?Node $node, array &$output): void { if ($node === null) return; $output[] = $node->value; preorder($node->left, $output); preorder($node->right, $output); }20$output = [];
    values this step[4, 2] → [4, 2, 1]output1node

  5. output ← [4, 2, 1, 3]

    18function list_string(array $values): string { return "[" . implode(", ", $values) . "]"; }19function preorder(?Node $node, array &$output): void { if ($node === null) return; $output[] = $node->value; preorder($node->left, $output); preorder($node->right, $output); }20$output = [];
    values this step[4, 2, 1] → [4, 2, 1, 3]output3node

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

    18function list_string(array $values): string { return "[" . implode(", ", $values) . "]"; }19function preorder(?Node $node, array &$output): void { if ($node === null) return; $output[] = $node->value; preorder($node->left, $output); preorder($node->right, $output); }20$output = [];
    values this step[4, 2, 1, 3] → [4, 2, 1, 3, 6]output6node

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

    18function list_string(array $values): string { return "[" . implode(", ", $values) . "]"; }19function preorder(?Node $node, array &$output): void { if ($node === null) return; $output[] = $node->value; preorder($node->left, $output); preorder($node->right, $output); }20$output = [];
    values this step[4, 2, 1, 3, 6] → [4, 2, 1, 3, 6, 5]output5node

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

    18function list_string(array $values): string { return "[" . implode(", ", $values) . "]"; }19function preorder(?Node $node, array &$output): void { if ($node === null) return; $output[] = $node->value; preorder($node->left, $output); preorder($node->right, $output); }20$output = [];
    values this step[4, 2, 1, 3, 6, 5] → [4, 2, 1, 3, 6, 5, 7]output7node

  9. echo list_string($output) . PHP_EOL;

    21preorder(sample_tree(), $output);22echo list_string($output) . PHP_EOL;23?>
    values this step[4, 2, 1, 3, 6, 5, 7]output

Complexity

  • Time: O(n)
  • Space: O(h) recursion stack

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)).
  • $output = [] is the traversal buffer, and preorder(?Node $node, array &$output): void receives it by reference.
  • The null guard if ($node === null) return; handles empty child links without appending anything.
  • Each non-null call appends first with $output[] = $node->value, then recurs into $node->left, then $node->right.
  • The trace starts with tree ready and empty output, then visits 4 before its children, producing [4].
  • The left subtree appends 2, then 1, then 3, giving [4, 2, 1, 3].
  • The right subtree appends 6, then 5, then 7, finishing [4, 2, 1, 3, 6, 5, 7].
  • echo list_string($output) . PHP_EOL prints [4, 2, 1, 3, 6, 5, 7].