Trees

BST Insert

Insert values into a binary search tree by comparing at each node.

Algorithm

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 insert_node(?Node $root, int $value): Node { if ($root === null) return new Node($value); if ($value < $root->value) $root->left = insert_node($root->left, $value); else $root->right = insert_node($root->right, $value); return $root; }
$root = null;
foreach ([4, 2, 6, 1, 3, 5, 7] as $value) $root = insert_node($root, $value);
echo render_tree($root) . PHP_EOL;
?>

BST insertion is a comparison path. The pinned tree 4(2(1,3),6(5,7)) is shown with the inserted value taking its sorted slot.

Step 1 - Start at root

For value 5, compare with 4 first; 5 is larger, so move right.

First comparison: 5 > 4, so the search for the insert slot goes right.insert 54compare26137

Step 2 - Take the left slot under 6

At 6, value 5 is smaller, so it becomes the left child.

Second comparison: 5 < 6, so the open left slot is used.426compare135new7

Step 3 - Canonical tree

The resulting tree is the pinned shape 4(2(1,3),6(5,7)).

Final BST after 5 is present under 6.4261357

Complexity

  • Time: O(h) per insert
  • Space: O(n)

Implementation notes

  • Nodes are PHP objects from class Node with typed properties: int $value, ?Node $left, and ?Node $right.
  • The constructor defaults both child links to null, so a new leaf starts with no children.
  • $root starts as null, then each value in [4, 2, 6, 1, 3, 5, 7] is inserted with $root = insert_node($root, $value).
  • insert_node(?Node $root, int $value): Node returns a node every time; the empty-subtree case creates new Node($value).
  • The comparison is $value < $root->value; smaller values recurse into $root->left, while equal-or-larger values use the right branch.
  • Child attachment is recursive assignment: $root->left = insert_node(...) or $root->right = insert_node(...).
  • The trace builds 4, then 4(2,_), 4(2,6), 4(2(1,3),6(5,_)), and finally 4(2(1,3),6(5,7)).
  • render_tree prints _ for a null child and value(left,right) for an internal node, so echo render_tree($root) . PHP_EOL prints 4(2(1,3),6(5,7)).
  • The replay also includes the sorted insert contrast [1, 2, 3, 4], which produces 1(_,2(_,3(_,4))) with height 4 and no rotation step.
binary search tree Values smaller than a node go left; larger values go right.