Есть ли способ удалить узел из BST без включения родительского узла в программу?

Question

Это для назначения в моем классе Data Structures, и мой профессор хочет, чтобы я создал метод удаления, который удаляет узел из дерева на основе целочисленного ключа. Если ключ не найден, то функция ничего не должна делать. Все примеры, которые я нашел, основывают свое дерево на наличии родительского, левого, правого узла. Эта программа имеет только левый и правый узел. Я попытался включить столько классов, сколько я думал, что они будут актуальны. Практически только методы печати деревьев были опущены.

public class BinarySearchTree
{

    private Node root;

    public BinarySearchTree() { this.root = null; }

    public BinarySearchTree ( Node root ) { this.root = root; }

    public void add ( Integer key, String value )
    {
        if (root == null)
            root = new Node( key, value);
        else
            root.add( key, value);
    }

    public boolean contains ( Integer key )
    {
        return root == null ? null : ( boolean ) root.contains( key );
    }

    public void remove ( Integer key )
    {

    }
}

public class Node
{
    public Node left;
    public Node right;
    public Integer key;
    public String value;

    public Node (String value, Node left, Node right)
    {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public Node (String value)
    {
        this.value = value;
        this.left = null;
        this.right = null;
    }

    public Node (Integer key, String value)
    {
        this.key = key;
        this.value = value;
    }

    public void add ( Integer key, String value )
    {
        if ( key.compareTo ( this.key ) < 0)
        {
            if ( left != null )
                left.add ( key, value );
            else
                left = new Node ( key, value );
        }
        else if ( key.compareTo ( this.key ) > 0 )
        {
            if ( right != null )
                right.add ( key, value );
            else
                right = new Node ( key, value);
        }
        else
            this.value = value;
    }

    public Serializable contains ( Integer key )
    {
        if ( this.key == ( key ) )
            return value;
        if ( key.compareTo ( this.key ) < 0 )
            return left == null ? null : left.contains ( key );
        else
            return right == null ? null : right.contains ( key );
    }

    public void remove ( Integer key )
    {

    }
}

Answer 1

Здесь remove() без Node класса, имеющего parent.

Node remove(Node root, int key) { 

    if (root == null)  return root; 

    if (key < root.key) 
        root.left = remove(root.left, key); 
    else if (key > root.key) 
        root.right = remove(root.right, key); 
    else { 
        // node with only one child or no child 
        if (root.left == null) 
            return root.right; 
        else if (root.right == null) 
            return root.left; 

        // node with two children: Get the inorder successor (smallest 
        // in the right subtree) 
        root.key = minValue(root.right); 

        // Delete the inorder successor 
        root.right = remove(root.right, root.key); 
    } 
    return root; 
}