// Notes on the deletion operation in trees, using a parent pointer

class Node // Node for binary search tree
{
    int  value;
    Node left;
    Node right;
    Node parent;

    Node (int x)
    {   value = x; }

    Node (int x, Node pa)  // insert with parent node
    {  
        value = x; 
        parent = pa;
    }

    void print() // print the information about the treenode
    {
        System.out.print(this);
        System.out.print(":  value: " + value);
        System.out.print("  left: " + left);
        System.out.print("  right: " + right);
        System.out.print("  parent: " + parent);
        System.out.println();
    }
}

class Tree // binary search tree
{
    Node root = null;  
    int size = 0;   // no. of elements stored in the tree

    Node findinsert(int x)
        // insert a new element if not present
        // return pointer to it
    {
        Node p = root, pa = null;  // pa = parent node
        while (p != null && p.value != x)
        {
            pa = p;
            if (x < p.value)
                p = p.left;
            else
                p = p.right;
        }
        if (p != null)  // item was found, end
            return p;

        p = new Node(x, pa);  // to be inserted
        if (root == null)  // have to change the root explicitly
            root = p;
        else
            if (x < pa.value)
                pa.left = p;
            else
                pa.right = p; 
        size ++;
        return p;
    }

    void print()  // print tree in order
    {
        recprint(root);
        System.out.println();
    }

    void recprint(Node p)
        // recursively print the tree values in sorted order
    {
        if (p == null)
            return;
        recprint (p.left);
        System.out.print(p.value + " ");
        recprint (p.right);
    }

    public static void main (String[] args)
        // process for testing as with lists in Ex. 5:
        // 0: print  >0:  insert  <0:  delete 
    { 
        Tree T = new Tree();
        int x=0;  // remember outside loop to see later if printed in loop
        for (int i=0; i < args.length; i++)
        {
            x = Integer.parseInt(args[i]);
            if (x == 0)
                T.print();
            else if (x>0) // insert
                T.findinsert(x);
            else // x < 0  delete
            {
                T.finddel(-x);
                T.print();
            }
        }
        if (x>0) // last operation was an insertion without print
            T.print();
    }



    void simpledel(Node p, boolean useleft)
        // delete a node by changing its parent
        // to point to left child if  useleft == true, o/w right child
    {
        Node pa = p.parent;
        if (pa == null)
            // change root node 
        {
            if (useleft)
                root = p.left;
            else
                root = p.right;
            if (root != null)
                root.parent = null;
        }
        else
        {
            // find out if node reached via left or right
            // from its parent
            if (p.value < pa.value) // is left child of parent
            {
                if (useleft)
                    pa.left = p.left;
                else
                    pa.left = p.right;
                if (pa.left != null)
                    pa.left.parent = pa;
            }
            
            else // is right child of parent
            {
                if (useleft)
                    pa.right= p.left;
                else
                    pa.right = p.right;
                if (pa.right != null)
                    pa.right.parent = pa;
            }
        }
    }

    void finddel(int x)
        // find and delete an item
    {
        Node p = root;
        while (p != null && p.value != x)
        {
            if (x < p.value)
                p = p.left;
            else
                p = p.right;
        }
        if (p == null)  // item was not found, end
            return;
        
        size --;
        if (p.right == null)  // no right child, easy to delete
            simpledel(p, true);
        else if (p.left == null)  // no left child, easy to delete
            simpledel(p, false);
        else  // find successor, replace that for current one
        {
            Node q = p.right;
            while (q.left != null)
                q = q.left;
            p.value = q.value;
            simpledel(q, false);
        }
    }
}