Двоичное дерево
Иерархическая структура данных, где у каждого узла не более двух потомков (левого и правого). Строительный блок для многих других структур.
Разновидности: двоичное дерево поиска (BST, упорядоченное), куча (родитель — максимум/минимум среди потомков), сбалансированное дерево (AVL, красно-чёрное, гарантированная высота), trie, дерево отрезков, дерево Фенвика. Обход: симметричный (in-order), прямой (pre-order), обратный (post-order), по уровням (BFS).
Несбалансированное BST может выродиться в связный список (операции за O(n)), поэтому в продакшене используют сбалансированные деревья: TreeMap в каждом языке — красно-чёрное дерево.