Как работает поиск по Бинарному дереву

Бинарный поиск в дереве работает за счет сравнения искомого значения с текущим узлом и рекурсивного спуска в левое или правое поддерево.

Алгоритм:

1. Начинаем с корня
2. Если искомое значение равно текущему узлу — возвращаем его
3. Если меньше — идем в левое поддерево
4. Если больше — в правое
5. Если дошли до nil — элемента нет

Пример на Go:

type Node struct {
    Value int
    Left  *Node
    Right *Node
}

func Search(root *Node, target int) *Node {
    if root == nil || root.Value == target {
        return root
    }
    if target < root.Value {
        return Search(root.Left, target)
    }
    return Search(root.Right, target)
}

Сложность: O(log n) в сбалансированном дереве, O(n) в худшем случае (вырожденное дерево).