type TreeNode struct {
    Value       int
    Left, Right *TreeNode
}

type BST struct {
    Root *TreeNode
}

func (t *BST) Insert(val int) {
    t.Root = insert(t.Root, val)
}

func insert(node *TreeNode, val int) *TreeNode {
    if node == nil {
        return &TreeNode{Value: val}
    }
    if val < node.Value {
        node.Left = insert(node.Left, val)
    } else if val > node.Value {
        node.Right = insert(node.Right, val)
    }
    return node
}

func (t *BST) Search(val int) bool {
    return search(t.Root, val)
}

func search(node *TreeNode, val int) bool {
    if node == nil {
        return false
    }
    switch {
    case val == node.Value:
        return true
    case val < node.Value:
        return search(node.Left, val)
    default:
        return search(node.Right, val)
    }
}

<?php
declare(strict_types=1);

final class TreeNode
{
    public ?TreeNode $left = null;
    public ?TreeNode $right = null;

    public function __construct(public readonly int $value) {}
}

final class BinarySearchTree
{
    public ?TreeNode $root = null;

    public function insert(int $val): void
    {
        $this->root = $this->insertNode($this->root, $val);
    }

    private function insertNode(?TreeNode $node, int $val): TreeNode
    {
        if ($node === null) {
            return new TreeNode($val);
        }

        if ($val < $node->value) {
            $node->left = $this->insertNode($node->left, $val);
        } elseif ($val > $node->value) {
            $node->right = $this->insertNode($node->right, $val);
        }
        return $node;
    }

    public function search(int $val): bool
    {
        return $this->searchNode($this->root, $val);
    }

    private function searchNode(?TreeNode $node, int $val): bool
    {
        if ($node === null) {
            return false;
        }
        return match (true) {
            $val === $node->value => true,
            $val < $node->value => $this->searchNode($node->left, $val),
            default => $this->searchNode($node->right, $val),
        };
    }
}

В PHP native бинарного дерева нет - пишем руками. Структура TreeNode тривиальна, поведение - в отдельном BinarySearchTree.

// Inorder: Left → Root → Right (отсортированный порядок!)
func inorder(node *TreeNode, result *[]int) {
    if node == nil {
        return
    }
    inorder(node.Left, result)
    *result = append(*result, node.Value)
    inorder(node.Right, result)
}

// Preorder: Root → Left → Right (для сериализации)
func preorder(node *TreeNode, result *[]int) {
    if node == nil {
        return
    }
    *result = append(*result, node.Value)
    preorder(node.Left, result)
    preorder(node.Right, result)
}

// Postorder: Left → Right → Root (для удаления)
func postorder(node *TreeNode, result *[]int) {
    if node == nil {
        return
    }
    postorder(node.Left, result)
    postorder(node.Right, result)
    *result = append(*result, node.Value)
}

// Level order (BFS)
func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }

    var result [][]int
    queue := []*TreeNode{root}

    for len(queue) > 0 {
        levelSize := len(queue)
        var level []int

        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            level = append(level, node.Value)

            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }

        result = append(result, level)
    }

    return result
}

<?php
declare(strict_types=1);

final class TreeTraversal
{
    /**
     * @param array<int> $result
     */
    public function inorder(?TreeNode $node, array &$result): void
    {
        if ($node === null) {
            return;
        }
        $this->inorder($node->left, $result);
        $result[] = $node->value;
        $this->inorder($node->right, $result);
    }

    /**
     * @param array<int> $result
     */
    public function preorder(?TreeNode $node, array &$result): void
    {
        if ($node === null) {
            return;
        }
        $result[] = $node->value;
        $this->preorder($node->left, $result);
        $this->preorder($node->right, $result);
    }

    /**
     * @param array<int> $result
     */
    public function postorder(?TreeNode $node, array &$result): void
    {
        if ($node === null) {
            return;
        }
        $this->postorder($node->left, $result);
        $this->postorder($node->right, $result);
        $result[] = $node->value;
    }

    /**
     * @return array<int, array<int>>
     */
    public function levelOrder(?TreeNode $root): array
    {
        if ($root === null) {
            return [];
        }

        $result = [];
        $queue = new \SplQueue();
        $queue->enqueue($root);

        while (!$queue->isEmpty()) {
            $levelSize = count($queue);
            $level = [];

            for ($i = 0; $i < $levelSize; $i++) {
                /** @var TreeNode $node */
                $node = $queue->dequeue();
                $level[] = $node->value;

                if ($node->left !== null) {
                    $queue->enqueue($node->left);
                }
                if ($node->right !== null) {
                    $queue->enqueue($node->right);
                }
            }

            $result[] = $level;
        }

        return $result;
    }
}