class Node{

public:
    Node *left;
    Node *right;
    Node *parent;
private:
    int value;
public:
    static void DFS(Node *node,int val)
    {
        if(node->left!=NULL)
            DFS(node->left, val);
        if(node->right!=NULL)
            DFS(node->right, val);
        if((node->value)==val)
        {

            if(node->left!=NULL)
            {
                //connect left child to the deleted node's parent
                if(node->parent!=NULL)
                {
                    if(node->parent->right==node)
                        node->parent->right = node->left;
                    else
                        if(node->parent->left==node)
                            node->parent->left = node->left;
                    node->left->parent = node->parent;
                }
                //connect right child to a leaf of the left child's subtree
                if(node->right!=NULL)
                {
                    Node *lf = returnLeaf(node->left);
                    node->right->parent = lf;
                    lf->right = node->right;
                }
            }
            else
                if(node->right!=NULL)
                {
                    //connect right child to the deleted node's parent
                    if(node->parent!=NULL)
                    {
                        if(node->parent->right==node)
                            node->parent->right = node->right;
                        else
                            if(node->parent->left==node)
                                node->parent->left = node->right;
                        node->right->parent = node->parent;
                    }

                    //connect left child to a leaf of the right child's subtree
                    if(node->left!=NULL)
                    {
                        Node *lf = returnLeaf(node->right);
                        node->left->parent = lf;
                        lf->right = node->right;
                    }
                }
            delete node;
        }
    }

    static Node* returnLeaf(Node *node)
    {
        //returns a leaf of the node's subtree
        if(node->left!=NULL)
            return returnLeaf(node->left);
        if(node->right!=NULL)
            return returnLeaf(node->right);
        return node;
    }

    static Node* removeNodes(Node *node, int value)
    {
        /*
            The question is very ambiguous, because I don't know what should
            I do with the children of a deleted node. Which one should I
            connect to the deleted node's parent? Or should let the graph
            disconnected after the deletion?

            I will connect one of the children to the node's parent,
            and the othe one to a leaf of the first child's subtree
        */

        //Solution:

        while(node->parent!=NULL)
            node = node->parent;
        //Now I am on the root
        DFS(node, value);
        return node;
    }


};