Trees

BST Search

Search a binary search tree for one present and one absent value.

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 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;
?>

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.

Present search path: 4 -> 6 -> 5.4#126#2135match7

Step 2 - Miss 8

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

Absent search path: 4 -> 6 -> 7 -> null.4#126#21357#3nullnot found

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.
search path A comparison chooses one subtree at each step, so whole branches are skipped.