Lesson4

#include <cassert>
#include <iostream>
#include <string>

using namespace std;

struct Node {
  int Data;
  Node* Left;
  Node* Right;
  Node(int data) : Data(data), Left(nullptr), Right(nullptr) {}
};

int DeleteMin(Node*& node) {
  assert(node != nullptr);
  if (node->Left == nullptr) {
    Node* todel = node;
    node = node->Right;
    int ans = todel->Data;
    delete todel;
    return ans;
  }
  return DeleteMin(node->Left);
}

void DeleteNode(Node*& node) {
  if (node->Left == nullptr) {
    Node* todel = node;
    node = node->Right;
    delete todel;
  } else if (node->Right == nullptr) {
    Node* todel = node;
    node = node->Left;
    delete todel;
  } else {
    int mn = DeleteMin(node->Right);
    node->Data = mn;
  }
}

// Удаление. Возвращает false, если нет узла с заданным ключом.
bool Delete(Node*& node, int value ) {
  if (node == 0) return false;
  if (node->Data == value) { // Нашли, удаляем.
    DeleteNode(node);
    return true;
  }
  return Delete(node->Data > value ? node->Left : node->Right, value);
}

void Print(Node* node, string prefix) {
  if (node == nullptr) return;
  Print(node->Right, prefix + "  ");
  cout << prefix << node->Data << "\n";
  Print(node->Left, prefix + "  ");
}

int main() {
  Node* root = new Node(6);
  root->Left = new Node(2);
  root->Right = new Node(10);
  root->Right->Left = new Node(8);
  Print(root, "");
  Delete(root, 6);
  Print(root, "");
  return 0;
}