Find Ancestor method for binary search tree is not working

Question

I had written the method for finding a node's parent in C# (c-sharp) but my code is not working correctly. Exceptions: System.NullReferenceException is thrown when I try to delete a node who's parent is null.

    public TreeNode FindParent(int value, ref TreeNode parent)
    {
        TreeNode currentNode = root;

        if (currentNode == null) 
        {
            return null;
        }

        while (currentNode.value != value)
        {
            if (value < currentNode.value)
            {
                parent = currentNode; 
                currentNode = currentNode.leftChild;  

            }
            if (value > currentNode.value)
            {
                parent = currentNode;  
                currentNode = currentNode.rightChild; 
            }
        }
        return currentNode;

    }


    public void Delete(int value)
    {
        TreeNode parent = null;
        TreeNode nodeToDelete = FindParent(value, ref parent);

        if (nodeToDelete == null)
        {
            throw new Exception("Unable to delete node: " + value.ToString());
        }



            //CASE 1: Nod has 0 children. 
        if (nodeToDelete.leftChild == null && nodeToDelete.rightChild == null) 
         {

                if (parent.leftChild == nodeToDelete) 
                {
                    parent.leftChild = null;
                }

                if (parent.rightChild == nodeToDelete) 
                {
                    parent.rightChild = null; 
                }
                count--; 
                return; 

            }
            //CASE 2: Nod has 1 left || 1 right barn 
            if (nodeToDelete.leftChild == null && nodeToDelete.rightChild != null)
            {
                nodeToDelete.rightChild = parent.rightChild;
                nodeToDelete = null;      
                count--;
                return; 

            }

            if (nodeToDelete.leftChild != null && nodeToDelete.rightChild == null)
            {
                nodeToDelete.leftChild = parent.leftChild;
                nodeToDelete = null;  
                count--;
                return; 

            }

            //CASE 3: Nod has 2 children 
            if (nodeToDelete.rightChild != null && nodeToDelete.leftChild != null)
            {
                TreeNode successor = LeftMostNodeOnRight(nodeToDelete, ref parent);
                TreeNode temp = new TreeNode(successor.value);
                if (parent.leftChild == successor)
                {
                    parent.leftChild = successor.rightChild;
                }
                else
                {
                    parent.rightChild = successor.rightChild; nodeToDelete.value = temp.value;
                }
                count--;
                return; 

            }

    }  

Answer 1

since you are using recursion , you don't need the parent Node to delete a node in a binary search tree, here is a delete method where you pass in int and the root

private BinaryTreeNode  remove (int value, TreeNode t){

    if(t==null)
        return t; // not found; do nothing

    if(value < t.value){
        t.left = remove(x,y,t.left);
    }
    else if (value > t.value){
        t.right = remove(x,y,t.right);
    }
    else if( t.left!=null && t.right != null) // two children
    {
        t.info = findMin(t.right).info; 
        remove(t.info.getLastName(),y,t.right);
    }
    else{                           // one child 
        if (t.left != null) { 
              t = t.left;
        }     
        else{ 
            t = t.right;
        }   
    }
    return t; 

}

Edit-----------findMin (find minimum node in a binary search tree)

private BinaryTreeNode  findMin ( BinaryTreeNode  t){  // recursive
        if(t == null)
            return null;
        else if (t.left == null)
            return t;
        return findMin(t.left);
    }

So you take the min value from the right subtree, and make it the parent of t.info. Follow these diagrams. We are deleting node 25 with two children.