Node flatten(Node &root, Node n, int rand){
    Node child = (rand) ? preNode(n) : postNode(n) ;
    Node p = child->parent;
    Node tmp = (child->left) ? child->left : child->right;
    if(tmp){
        tmp->parent = p;
    }
    if(p == NULL){
        root = tmp;
    }
    if(p->left == child){
        p->left = tmp;
    } else if(p->right == child){
        p->right = tmp;
    }


    return child;

}


Node removeNode(Node &root, Node n){
    if(n == NULL) return NULL;
    Node p = n->parent;
    Node tmp;
    if(n->left && n->right){
        tmp = flatten(root, n, rand()%2);
        tmp->left = n->left; if(n->left != NULL){ n->left->parent = tmp; };
        tmp->right = n->right; if(n->right != NULL){ n->right->parent = tmp; };
    } else {
        tmp = (n->left) ? n->left : n->right;
    }
    if(tmp){ // jak zmienna jest lisciem to nie wstawiac parent
        tmp->parent = p;
    }
    if(p == NULL){ // jak rodzic jest rootem
        root = tmp;
    } else if(p->left == n){
        p->left = tmp;
    } else if(p->right == n){
        p->right = tmp;
    }

    return n;

}