Build a Binary Tree

Create a fixed seven-node binary tree and render its shape.

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) . "]"; }
echo render_tree(sample_tree()) . PHP_EOL;
?>

Complexity

Time: O(n)
Space: O(n)

Implementation notes

Nodes are PHP objects from class Node with typed properties: int $value, ?Node $left, and ?Node $right.
The constructor accepts optional child objects, defaulting both links to null for leaf nodes.
sample_tree() builds the whole tree with nested new Node(...) calls: root 4, left child 2(1,3), and right child 6(5,7).
The trace records construction from leaves toward parents: node 1, node 3, then node 2 as 2(1,3).
The right side follows the same pattern with node 5, node 7, then node 6 as 6(5,7).
The final constructed root is node 4, producing 4(2(1,3),6(5,7)).
render_tree(?Node $node) returns _ for null, a bare value for a leaf, and value(left,right) for an internal node.
echo render_tree(sample_tree()) . PHP_EOL prints the compact tree string 4(2(1,3),6(5,7)).

node links A node stores one value plus references to its left and right children.