5
\$\begingroup\$

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;


}
\$\endgroup\$
  • \$\begingroup\$ These carry handling. Try to use switch statements to make it more readable. \$\endgroup\$ – DrProgrammer Nov 22 '15 at 21:52
  • \$\begingroup\$ There is no such thing as an if "loop". \$\endgroup\$ – Eric Stein Nov 22 '15 at 22:31
  • \$\begingroup\$ Yeah I wrote it by mistake. Can you have a look at my code? \$\endgroup\$ – Himanshu Verma Nov 23 '15 at 2:07
  • \$\begingroup\$ left.key = minNode.key; node.parent.right.right = minNode.right; is probably erroneous as well as dispensable: in effect, all three cases with node->right == minNode (minNode.parent == node) are identical: just use the first notation. ((node->right == minNode) == (null == node->right->left)) null == minNode->left does not mean that you need to keep minNode and minNode->right, only: in the minNode.parent != node branch, there's at least node->right, which may or may not be minNode.parent, and possibly quite a lot more, and both handlings look wrong. \$\endgroup\$ – greybeard Jan 11 '16 at 19:30
  • \$\begingroup\$ deleteNode() looks very similar to AnkitSablok's question re. Dictionary implemented using a Binary Search Tree - is there a text book/other reference it would be of advantage for readers of both questions to know? \$\endgroup\$ – greybeard Jan 12 '16 at 9:32
2
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.