50
      /  \
    30    70
   / \   / \
  20 40 60 80

       50
      /  \
    30    70
   / \
  20 60  ❌ 60 має бути у правому піддереві 50, а не в лівому!

struct TreeNode
{
    int data;           // Значення вузла
    TreeNode* left;     // Покажчик на ліве піддерево (менші значення)
    TreeNode* right;    // Покажчик на праве піддерево (більші значення)
    
    // Конструктор для зручності
    TreeNode(int value)
        : data(value), left(nullptr), right(nullptr)
    {
    }
};

// BinarySearchTree.h
#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H

#include <iostream>

struct TreeNode
{
    int data;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(int value)
        : data(value), left(nullptr), right(nullptr)
    {
    }
};

class BinarySearchTree
{
private:
    TreeNode* root;  // Покажчик на корінь дерева
    
    // Приватні рекурсивні допоміжні методи
    TreeNode* insertRecursive(TreeNode* node, int value);
    TreeNode* deleteRecursive(TreeNode* node, int value);
    TreeNode* findMin(TreeNode* node) const;
    bool searchRecursive(TreeNode* node, int value) const;
    void inOrderRecursive(TreeNode* node) const;
    void preOrderRecursive(TreeNode* node) const;
    void postOrderRecursive(TreeNode* node) const;
    void destroyTree(TreeNode* node);
    int heightRecursive(TreeNode* node) const;

public:
    // Конструктор: створює порожнє дерево
    BinarySearchTree();
    
    // Деструктор: видаляє всі вузли (RAII)
    ~BinarySearchTree();
    
    // Заборона копіювання (для простоти)
    BinarySearchTree(const BinarySearchTree&) = delete;
    BinarySearchTree& operator=(const BinarySearchTree&) = delete;
    
    // Вставити значення в дерево
    void insert(int value);
    
    // Видалити значення з дерева
    void remove(int value);
    
    // Пошук значення в дереві
    bool search(int value) const;
    
    // Перевірити, чи дерево порожнє
    bool isEmpty() const;
    
    // Отримати висоту дерева
    int height() const;
    
    // Обходи дерева
    void inOrder() const;    // Впорядкований: ліве → корінь → праве
    void preOrder() const;   // Префіксний: корінь → ліве → праве
    void postOrder() const;  // Постфіксний: ліве → праве → корінь
};

#endif

// BinarySearchTree.cpp
#include "BinarySearchTree.h"

// Конструктор: ініціалізує порожнє дерево
BinarySearchTree::BinarySearchTree()
    : root(nullptr)
{
}

// Деструктор: видаляє всі вузли (post-order обхід)
BinarySearchTree::~BinarySearchTree()
{
    destroyTree(root);
}

// Рекурсивне видалення всього дерева
void BinarySearchTree::destroyTree(TreeNode* node)
{
    if (node == nullptr)
    {
        return;  // Базовий випадок: порожнє дерево
    }
    
    // Рекурсивно видаляємо ліве та праве піддерева
    destroyTree(node->left);
    destroyTree(node->right);
    
    // Тепер можна видалити поточний вузол
    delete node;
}

// Публічний метод (обгортка)
void BinarySearchTree::insert(int value)
{
    root = insertRecursive(root, value);
}

// Приватний рекурсивний метод
TreeNode* BinarySearchTree::insertRecursive(TreeNode* node, int value)
{
    // Базовий випадок: дійшли до nullptr — створюємо новий вузол
    if (node == nullptr)
    {
        return new TreeNode(value);
    }
    
    // Рекурсивний випадок: вибираємо напрямок
    if (value < node->data)
    {
        // Значення менше — йдемо ліворуч
        node->left = insertRecursive(node->left, value);
    }
    else if (value > node->data)
    {
        // Значення більше — йдемо праворуч
        node->right = insertRecursive(node->right, value);
    }
    else
    {
        // value == node->data — дублікат, не вставляємо
        std::cerr << "Значення " << value << " вже існує в дереві\n";
    }
    
    // Повертаємо вказівник на поточний вузол (незмінний для рекурсивного виклику)
    return node;
}

// Публічний метод
bool BinarySearchTree::search(int value) const
{
    return searchRecursive(root, value);
}

// Приватний рекурсивний метод
bool BinarySearchTree::searchRecursive(TreeNode* node, int value) const
{
    // Базовий випадок 1: дійшли до nullptr — значення не знайдено
    if (node == nullptr)
    {
        return false;
    }
    
    // Базовий випадок 2: знайшли значення
    if (value == node->data)
    {
        return true;
    }
    
    // Рекурсивний випадок: вибираємо напрямок
    if (value < node->data)
    {
        return searchRecursive(node->left, value);   // Шукаємо ліворуч
    }
    else
    {
        return searchRecursive(node->right, value);  // Шукаємо праворуч
    }
}

bool BinarySearchTree::search(int value) const
{
    TreeNode* current = root;
    
    while (current != nullptr)
    {
        if (value == current->data)
        {
            return true;  // Знайдено
        }
        else if (value < current->data)
        {
            current = current->left;   // Йдемо ліворуч
        }
        else
        {
            current = current->right;  // Йдемо праворуч
        }
    }
    
    return false;  // Дійшли до nullptr — не знайдено
}

Видалити 20:
       50
      /  \
    30    70
   /  \
  20  40   →  Просто delete 20, встановити left = nullptr

Видалити 30 (має лише праву дитину 40):
       50                    50
      /  \                  /  \
    30    70    →         40    70
      \
      40

Видалити 50 (має двох дітей):
       50                    60  ← Копіюємо 60 сюди
      /  \                  /  \
    30    70    →         30    70
         / \                     \
        60  80                   80
        
Потім рекурсивно видаляємо 60 з правого піддерева (випадок 2 або 1)

// Публічний метод
void BinarySearchTree::remove(int value)
{
    root = deleteRecursive(root, value);
}

// Приватний рекурсивний метод
TreeNode* BinarySearchTree::deleteRecursive(TreeNode* node, int value)
{
    // Базовий випадок: дійшли до nullptr — значення не знайдено
    if (node == nullptr)
    {
        return nullptr;
    }
    
    // Рекурсивний пошук вузла для видалення
    if (value < node->data)
    {
        node->left = deleteRecursive(node->left, value);
    }
    else if (value > node->data)
    {
        node->right = deleteRecursive(node->right, value);
    }
    else
    {
        // Знайшли вузол для видалення
        
        // Випадок 1: Вузол-лист (без дітей)
        if (node->left == nullptr && node->right == nullptr)
        {
            delete node;
            return nullptr;
        }
        
        // Випадок 2a: Вузол має лише праву дитину
        if (node->left == nullptr)
        {
            TreeNode* temp = node->right;
            delete node;
            return temp;
        }
        
        // Випадок 2b: Вузол має лише ліву дитину
        if (node->right == nullptr)
        {
            TreeNode* temp = node->left;
            delete node;
            return temp;
        }
        
        // Випадок 3: Вузол має двох дітей
        // Знаходимо in-order наступника (мінімум у правому піддереві)
        TreeNode* successor = findMin(node->right);
        
        // Копіюємо значення наступника у поточний вузол
        node->data = successor->data;
        
        // Рекурсивно видаляємо наступника з правого піддерева
        node->right = deleteRecursive(node->right, successor->data);
    }
    
    return node;
}

// Допоміжний метод: знайти мінімальний вузол у піддереві
TreeNode* BinarySearchTree::findMin(TreeNode* node) const
{
    while (node->left != nullptr)
    {
        node = node->left;  // Йдемо максимально ліворуч
    }
    return node;
}

void BinarySearchTree::inOrder() const
{
    inOrderRecursive(root);
    std::cout << '\n';
}

void BinarySearchTree::inOrderRecursive(TreeNode* node) const
{
    if (node == nullptr)
    {
        return;  // Базовий випадок
    }
    
    inOrderRecursive(node->left);        // 1. Обійти ліве піддерево
    std::cout << node->data << " ";      // 2. Відвідати корінь
    inOrderRecursive(node->right);       // 3. Обійти праве піддерево
}

In-Order: 20 30 40 50 60 70 80  ← Відсортовано!

void BinarySearchTree::preOrder() const
{
    preOrderRecursive(root);
    std::cout << '\n';
}

void BinarySearchTree::preOrderRecursive(TreeNode* node) const
{
    if (node == nullptr)
    {
        return;
    }
    
    std::cout << node->data << " ";      // 1. Відвідати корінь
    preOrderRecursive(node->left);       // 2. Обійти ліве піддерево
    preOrderRecursive(node->right);      // 3. Обійти праве піддерево
}

Pre-Order: 50 30 20 40 70 60 80

void BinarySearchTree::postOrder() const
{
    postOrderRecursive(root);
    std::cout << '\n';
}

void BinarySearchTree::postOrderRecursive(TreeNode* node) const
{
    if (node == nullptr)
    {
        return;
    }
    
    postOrderRecursive(node->left);       // 1. Обійти ліве піддерево
    postOrderRecursive(node->right);      // 2. Обійти праве піддерево
    std::cout << node->data << " ";       // 3. Відвідати корінь
}

Post-Order: 20 40 30 60 80 70 50

// Публічний метод
int BinarySearchTree::height() const
{
    return heightRecursive(root);
}

// Приватний рекурсивний метод
int BinarySearchTree::heightRecursive(TreeNode* node) const
{
    // Базовий випадок: порожнє дерево
    if (node == nullptr)
    {
        return -1;
    }
    
    // Рекурсивно обчислюємо висоту лівого та правого піддерев
    int leftHeight = heightRecursive(node->left);
    int rightHeight = heightRecursive(node->right);
    
    // Висота поточного вузла = максимум висот дітей + 1
    return std::max(leftHeight, rightHeight) + 1;
}

#include "BinarySearchTree.h"
#include <iostream>

int main()
{
    BinarySearchTree bst;
    
    std::cout << "=== Демонстрація бінарного дерева пошуку ===\n\n";
    
    // Вставка елементів
    std::cout << "Вставка елементів: 50, 30, 70, 20, 40, 60, 80\n";
    bst.insert(50);
    bst.insert(30);
    bst.insert(70);
    bst.insert(20);
    bst.insert(40);
    bst.insert(60);
    bst.insert(80);
    
    // Обходи дерева
    std::cout << "\nОбходи дерева:\n";
    std::cout << "In-Order (відсортовано):   ";
    bst.inOrder();   // 20 30 40 50 60 70 80
    
    std::cout << "Pre-Order (корінь спершу): ";
    bst.preOrder();  // 50 30 20 40 70 60 80
    
    std::cout << "Post-Order (корінь останнім): ";
    bst.postOrder(); // 20 40 30 60 80 70 50
    
    // Висота дерева
    std::cout << "\nВисота дерева: " << bst.height() << '\n';
    
    // Пошук елементів
    std::cout << "\nПошук елемента 40: " 
              << (bst.search(40) ? "знайдено ✓" : "не знайдено ✗") << '\n';
    std::cout << "Пошук елемента 99: " 
              << (bst.search(99) ? "знайдено ✓" : "не знайдено ✗") << '\n';
    
    // Видалення елементів
    std::cout << "\nВидалення елемента 20 (лист)\n";
    bst.remove(20);
    std::cout << "In-Order після видалення: ";
    bst.inOrder();   // 30 40 50 60 70 80
    
    std::cout << "\nВидалення елемента 30 (одна дитина)\n";
    bst.remove(30);
    std::cout << "In-Order після видалення: ";
    bst.inOrder();   // 40 50 60 70 80
    
    std::cout << "\nВидалення елемента 50 (дві дитини, корінь)\n";
    bst.remove(50);
    std::cout << "In-Order після видалення: ";
    bst.inOrder();   // 40 60 70 80
    
    return 0;
}

BinarySearchTree bst;
bst.insert(10);
bst.insert(20);
bst.insert(30);
bst.insert(40);
bst.insert(50);

10
  \
   20
     \
      30
        \
         40
           \
            50