Trees

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.

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

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

  1. node ← 1, tree ← 1

    15function sample_tree(): Node {16    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));17}
    values this step1node1tree

  2. node ← 3, tree ← 1, 3

    15function sample_tree(): Node {16    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));17}
    values this step3node1, 3tree

  3. node ← 2, tree ← 2(1,3)

    15function sample_tree(): Node {16    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));17}
    values this step2node2(1,3)tree

  4. node ← 5, tree ← 2(1,3), 5

    15function sample_tree(): Node {16    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));17}
    values this step5node2(1,3), 5tree

  5. node ← 7, tree ← 2(1,3), 5, 7

    15function sample_tree(): Node {16    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));17}
    values this step7node2(1,3), 5, 7tree

  6. node ← 6, tree ← 2(1,3), 6(5,7)

    15function sample_tree(): Node {16    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));17}
    values this step6node2(1,3), 6(5,7)tree

  7. node ← 4, tree ← 4(2(1,3),6(5,7))

    15function sample_tree(): Node {16    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));17}
    values this step4node4(2(1,3),6(5,7))tree

  8. stdout ← 4(2(1,3),6(5,7))

    18function list_string(array $values): string { return "[" . implode(", ", $values) . "]"; }19echo render_tree(sample_tree()) . PHP_EOL;20?>
    values this step4(2(1,3),6(5,7))stdout4(2(1,3),6(5,7))tree

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