Binary Search tree deletion optimization

Question

I have just started implementing Binary Search tree on my own without using any tutorials online. Please have a look and suggest how can I make code less cluttered and more faster. Right now I am using lots of if-else conditions and want to remove them as much as I can.

boolean deleteNode(int data, TreeNode node )
{
    if( data < node.key) deleteNode(data, node.left);
    else if( data > node.key) deleteNode(data, node.right);

    else {
        System.out.println("Value of node = " + node.key);
        //case 1 - Left and Right is null - Leaves
        if(node.left == null && node.right == null)
        { 
            if(node == node.parent.left)node.parent.left =  null;
            else node.parent.right = null;
            System.out.println("Inside first if");
        }

        //case 2 - One child is null

        else if(node.left !=null && node.right ==null)

        {
            if(node == node.parent.left)node.parent.left = node.left;
            else node.parent.right = node.left;

        }
        else if(node.right !=null && node.left ==null)
        {
            if(node == node.parent.right)node.parent.right = node.right;
            else node.parent.left = node.right;             
        }

        //case 3 - Delete node is an internal node

        else if(node.left !=null && node.right !=null)
        {
            TreeNode minNode = treeMin(node.right);

            if(minNode.parent == node)
            {
                if(node.parent == null)
                    {
                        node.key = minNode.key;
                        node.right = minNode.right;
                    }
                else{
                if(node == node.parent.left)
                    {
                        node.parent.left.key = minNode.key;
                        node.parent.right.right = minNode.right;

                    }
                if(node == node.parent.right)
                    {
                        node.parent.right.key = minNode.key;
                        node.parent.right.right = minNode.right;
                    }
                }
            }

            else
            {
                if(node == node.parent.left)
                {
                    node.parent.left.key = minNode.key;
                    node.left.right = minNode.right;

                }
                else if(node == node.parent.right)
                {

                    node.parent.right.key = minNode.key;
                    node.right.left = minNode.right;

                }
            }
        }


    }
    return true;


}

Answer 1

You are always returning true so I guess you don't really need current return value. In that case you might want to try a bit different approach. You want to do something like:

 if( data < node.key) {
    node.left = deleteNode(data, node.left);
 } else if( data > node.key) {
    node.right = deleteNode(data, node.right);
 } else {
    //here return resulting node after deletion, null if node had no children
 }

That way you don't need to know anything about parent

Answer 2

I think that user158037's observation about the value you returned is directly related to a glaring omission:
The code is not documented. In particular, it doesn't say what deleteNode(int data, TreeNode node) is to accomplish (e.g., when null == node), or return.
Don't be afraid to provide too much context: the snippet contains little clue whether it is a member of TreeNode (tried that: got unwieldy for lack of use this node instead).

Postpone faster until you are comfortable with your model of tree and node and the way your code implements it - and you have specific cause to worry about run time.

The code below picks up user158037's suggestion to return the new root:

 /** delete {@code data} from binary search tree
  *  rooted at {@code node}, if present
  * @return root after deletion */
 // could be static but for override
    TreeNode deleteNode(int data, TreeNode node)
    {
        if (null == node)
            return null;
        if (data != node.key) {
            if (data < node.key)
                node.left = deleteNode(data, node.left);
            else // (data > node.key)
                node.right = deleteNode(data, node.right);
            return node;
        }

//      System.out.println("Value of node = " + node.key);
        if (null == node.left) {
            if (null == node.right) {
            // case 1 - Left and Right is null - Leaves
//              System.out.println("left and right null");
            } else {
            // case 2 - node has one child
            }
            return node.right;
        }
        TreeNode parent = node.right;
        if (parent == null) {
        // case 2 - node has one child
            return node.left;
        }
    // case 3 - node is an internal node
        TreeNode child = parent.left;
        if (null == child) {
        // almost simple: node.right is the leftmost node in its tree
            node.right = parent.right;
        } else {
            TreeNode grand = parent = node.left;
            if (null == parent.right) {
            // symmetrical: node.left is rightmost in its tree
                node.left = parent.left;
            } else {
            // find rightmost descendant to the left
                while (null != (child = parent.right)) {
                    grand = parent;
                    parent = child;
                }
            // replace rightmost descendant to the left
            //  by its left subtree ...
                grand.right = parent.left;
            }
        }
    // ... and replace node's key by that
    //  of its "most easily found" closest descendant 
        node.key = parent.key;
        return node;
    }

(If you use tracing: use a package, and consider tracing run-time comments.)
If node needs to be replaced, this manipulates the key instead, just like the code in the question. The right thing to do would be to replace node by one of its neighbours (parent in the snippet presented), requiring more reference manipulation.
(Don't do as I do: do as I say ;-)
I find it difficult to "return more than one value" from a Java function member - a natural with PostScript - contributing to the difficulty to specify&code a useful node delete in a class of a basic tree implementation.