🌲 Binary Search Tree (BST)

<?php
class BSTNode {
    public int $val;
    public ?BSTNode $left = null, $right = null;
    public function __construct(int $val) { $this->val = $val; }
}

class BST {
    public ?BSTNode $root = null;

    // Insert - O(log n) avg, O(n) worst
    public function insert(int $val): void {
        $this->root = $this->insertRec($this->root, $val);
    }

    private function insertRec(?BSTNode $node, int $val): BSTNode {
        if ($node === null) return new BSTNode($val);
        if ($val < $node->val) $node->left = $this->insertRec($node->left, $val);
        else $node->right = $this->insertRec($node->right, $val);
        return $node;
    }

    // Search - O(log n) avg, O(n) worst
    public function search(int $val): bool {
        return $this->searchRec($this->root, $val) !== null;
    }

    private function searchRec(?BSTNode $node, int $val): ?BSTNode {
        if ($node === null || $node->val === $val) return $node;
        if ($val < $node->val) return $this->searchRec($node->left, $val);
        return $this->searchRec($node->right, $val);
    }

    // Delete - O(log n) avg
    public function delete(int $val): void {
        $this->root = $this->deleteRec($this->root, $val);
    }

    private function deleteRec(?BSTNode $node, int $val): ?BSTNode {
        if ($node === null) return null;

        if ($val < $node->val) $node->left = $this->deleteRec($node->left, $val);
        elseif ($val > $node->val) $node->right = $this->deleteRec($node->right, $val);
        else {
            // Case 1 & 2: 0 or 1 child
            if ($node->left === null) return $node->right;
            if ($node->right === null) return $node->left;
            // Case 3: 2 children - find inorder successor
            $minNode = $this->findMin($node->right);
            $node->val = $minNode->val;
            $node->right = $this->deleteRec($node->right, $minNode->val);
        }
        return $node;
    }

    private function findMin(BSTNode $node): BSTNode {
        while ($node->left !== null) $node = $node->left;
        return $node;
    }

    // Validate BST
    public function isValidBST(): bool {
        return $this->validate($this->root, PHP_INT_MIN, PHP_INT_MAX);
    }

    private function validate(?BSTNode $node, int $min, int $max): bool {
        if ($node === null) return true;
        if ($node->val <= $min || $node->val >= $max) return false;
        return $this->validate($node->left, $min, $node->val)
            && $this->validate($node->right, $node->val, $max);
    }

    // Inorder gives sorted order!
    public function inorder(): array {
        $result = []; $this->inorderRec($this->root, $result);
        return $result;
    }

    private function inorderRec(?BSTNode $node, array &$result): void {
        if ($node === null) return;
        $this->inorderRec($node->left, $result);
        $result[] = $node->val;
        $this->inorderRec($node->right, $result);
    }
}

$bst = new BST();
foreach ([8,3,10,1,6,14,4,7,13] as $v) $bst->insert($v);
var_dump($bst->search(6));   // true
var_dump($bst->search(99)); // false
print_r($bst->inorder());    // [1,3,4,6,7,8,10,13,14] - SORTED!
var_dump($bst->isValidBST()); // true