BST Search - PHP DSA

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.

search path A comparison chooses one subtree at each step, so whole branches are skipped.

Visual walkthrough

A BST search follows one comparison path. The same pinned tree shows a found path for 5 and a missing path for 8.

Step 1 - Find 5

Search 5 takes right from 4, then left from 6, then matches 5.

Step 2 - Miss 8

Search 8 takes right from 4, right from 6, right from 7, then reaches null.

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 search_tree(?Node $root, int $target): bool { $node = $root; while ($node !== null) { if ($target === $node->value) return true; $node = $target < $node->value ? $node->left : $node->right; } return false; }
$root = sample_tree();
echo (search_tree($root, 5) ? "5 found" : "5 not found") . PHP_EOL;
echo (search_tree($root, 8) ? "8 found" : "8 not found") . PHP_EOL;
?>

                        

Complexity

Time: O(h) per search
Space: O(1) iterative

Implementation notes

Nodes are PHP objects from class Node with typed int $value plus nullable ?Node $left and ?Node $right links.
sample_tree() constructs the checked tree directly as 4(2(1,3),6(5,7)).
search_tree(?Node $root, int $target): bool is iterative: it starts with $node = $root and runs while $node !== null.
A strict match check, $target === $node->value, returns true immediately.
Otherwise the cursor moves with the ternary $target < $node->value ? $node->left : $node->right.
The successful search target is 5: the trace moves from cursor 4 right, then cursor 6 left, then matches cursor 5.
The miss target is 8: the trace moves from 4 right, 6 right, 7 right, then reaches null and returns false.
The search reads object links but does not mutate the tree.
The two echo calls format boolean results as text, printing 5 found and then 8 not found on the next line.