Деревья и binary search trees

Trees представляют hierarchy через parent-child edges. Binary trees ограничивают node левым и правым child; binary search trees добавляют ordering invariant. Traversal order важен: preorder удобен для serialization, inorder показывает sorted BST values, а postorder помогает delete или aggregate children first.

Компромисс: сравните время, память и сложность реализации до выбора структуры или паттерна.

На интервью: Интервьюеры ожидают base cases, объяснение recursion depth и различие general binary tree от balanced search tree.

Типовые ошибки: Skewed BST является linked list с O(n) operations. Не валидируйте BST проверкой только immediate children; передавайте min и max bounds через recursion.

Чеклист:

• Выберите traversal order.
• Отслеживайте depth и stack space.
• Передавайте BST bounds.
• Обработайте null children.