#include "pt4.h"
using namespace std;

void deleteNode(PNode& tree);

PNode searchNode(PNode tree);

PNode searchRoot(PNode tree);

void Solve()
{
    Task("Tree71");
    PNode ptr;
    pt >> ptr;
    PNode root = searchRoot(ptr);
    if (root == ptr) {
        deleteNode(root);
    } else {
        deleteNode(ptr);
    }
    pt << root;
}

void deleteNode(PNode& tree) {
    PNode temp;
    if (tree->Left == nullptr) {
        if (tree->Parent != nullptr) {
            if (tree->Parent->Left == tree) {
                tree->Parent->Left = tree->Right;
            } else {
                tree->Parent->Right = tree->Right;
            }
        }
        if (tree->Right != nullptr) {
            tree->Right->Parent = tree->Parent;
        }
        temp = tree->Right;
        delete tree;
        tree = temp;
    } else if (tree->Right == nullptr) {
        if (tree->Parent != nullptr) {
            if (tree->Parent->Left == tree) {
                tree->Parent->Left = tree->Left;
            } else {
                tree->Parent->Right = tree->Left;
            }
        }
        if (tree->Left != nullptr) {
            tree->Left->Parent = tree->Parent;
        }
        temp = tree->Left;
        delete tree;
        tree = temp;
    } else {
        PNode del = searchNode(tree->Right);
        if (del->Parent != tree) {
            del->Parent->Left = del->Right;
        } else {
            tree->Right = del->Right;
        }
        if (del->Right != nullptr) {
            del->Right->Parent = del->Parent;
        }
        tree->Data = del->Data;
        delete del;
    }
}

PNode searchNode(PNode tree) {
    if (tree->Left == nullptr) {
        return tree;
    }
    return searchNode(tree->Left);
}

PNode searchRoot(PNode tree) {
    if (tree->Parent == nullptr) {
        return tree;
    }
    return searchRoot(tree->Parent);
}