Реализация двоичного дерева

16. Реализовать простое двоичное дерево поиска

Условие задачи:
Необходимо реализовать простое двоичное дерево поиска (Binary Search Tree, BST).

Дерево должно поддерживать:

добавление элементов;
обход in-order: левое поддерево → текущий узел → правое поддерево.

Для BST выполняется правило:

значения меньше текущего хранятся слева;
значения больше текущего хранятся справа.

При in-order обходе значения BST выводятся в отсортированном порядке.

Пример:

Вход:
[5, 3, 7, 2, 4, 6, 8]

Дерево:

        5
       / \
      3   7
     / \ / \
    2  4 6  8

Результат:
[2, 3, 4, 5, 6, 7, 8]

Спойлеры к решению

Подсказки

💡 Каждый узел хранит значение и ссылки на левый и правый дочерние узлы.
💡 При вставке значения меньше текущего узла идут влево, больше — вправо.
💡 Для in-order обхода сначала рекурсивно обойди левое поддерево, затем текущий узел, затем правое.
💡 Дубликаты нужно обработать явно — в простом варианте их можно не добавлять.

Решение

public class BinarySearchTree {

    private static class Node {
        private final int value;
        private Node left;
        private Node right;

        private Node(int value) {
            this.value = value;
        }
    }

    private Node root;

    public void insert(int value) {
        root = insert(root, value);
    }

    private Node insert(Node node, int value) {
        if (node == null) {
            return new Node(value);
        }

        if (value < node.value) {
            node.left = insert(node.left, value);
        } else if (value > node.value) {
            node.right = insert(node.right, value);
        }

        return node;
    }

    public List<Integer> inOrder() {
        List<Integer> result = new ArrayList<>();
        inOrder(root, result);
        return result;
    }

    private void inOrder(Node node, List<Integer> result) {
        if (node == null) {
            return;
        }

        inOrder(node.left, result);
        result.add(node.value);
        inOrder(node.right, result);
    }
}

Пример использования:

BinarySearchTree tree = new BinarySearchTree();

tree.insert(5);
tree.insert(3);
tree.insert(7);
tree.insert(2);
tree.insert(4);
tree.insert(6);
tree.insert(8);

System.out.println(tree.inOrder());

Результат:

[2, 3, 4, 5, 6, 7, 8]

При вставке:

if (value < node.value) {
    node.left = insert(node.left, value);
} else if (value > node.value) {
    node.right = insert(node.right, value);
}

значение рекурсивно направляется в левое или правое поддерево.

Если значение уже существует, новая вершина не создаётся.

in-order обход выполняется в порядке:

inOrder(node.left, result);
result.add(node.value);
inOrder(node.right, result);

Поэтому для двоичного дерева поиска результат будет отсортирован по возрастанию.

Сложность вставки зависит от высоты дерева h:

в среднем — O(log n);
в худшем случае, если дерево вырождается в список, — O(n).

Обход всего дерева занимает O(n). Дополнительная память рекурсивного обхода — O(h) плюс O(n) для результирующего списка.