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.

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) . "]"; }
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;
?>

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].
preorder Preorder records the current node before visiting left and right subtrees.