Java: Binary Search Tree

Question

I decided to create a Binary Search Tree using java, and what I want to do is delete the Max element from the tree, so I created this part of code:

public Node<T> removeMax(Node<T> node) {
    if (node == null)
        return null;
    if (node.right == null) {
        Node<T> n = node;
        node = null;
        return n;
    }

    return removeMax(node.right);
}

The method returns the Max element, but it doesn't remove it from the tree. As you can see, I tried to remove it in this part:

Node<T> n = node;
node = null;
return n;

But, when I print the elements in the tree, it shows the "removed" ones too. What am I doing wrong?

EDIT: What I'm really trying to do is delete the Max node and return it so I can now which one was deleted.

Could this be a problem with mutability? If it is, then just changing `return n` to `return node` might fix it. — johmsp, Jun 20 '16 at 15:24
The problem is that node=null has no effect here as `node` is a copy of the pointer of your original tree. What you want to do is : `if(node.right.right==null){ Node n = node.right; node.right = null; return n; }` — Omar, Jun 20 '16 at 15:26
Good related reading: http://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value — , Jun 20 '16 at 15:38
@Omar and how is node.right.right or node.right a copy of a pointer if just node isn't. It's really not clear to me! — Asker, Jun 20 '16 at 15:59
@Asker When you call removeMax(node.right), the pointer node.right is copied on the virtual machine stack, so when you enter once again in the method, `node` is a copy of node.right but both points to the same value of course. That's why when you do `node = null`, nothing happens because you modify a copy. For example, in Java, you cannot write a method which switch two values, for the same reasons — Omar, Jun 20 '16 at 16:41

Nazareth Keshishian · Answer 1 · 2018-10-26T16:43:14.860

Now I noticed you wanted to know which node gets deleted. All you can do is to delete the maximum node and print the tree:

 public void deleteMax(Node<T> root) { 
         Node<T> current = root;
         while (current.right.right != null) { 
             current = current.right; 
         } 
         if(current.right.left!=null) {//max has 1 child to left
             current.right=current.right.left;
         }
         else {//max has no child
             current.right=null;
         }
     }

public String printInfix(Node<T> root) {//prints all the data in the tree in infix order

   if(root==null) {
        return "";
   }

 return printAll(root.left+" "+root.data+" "+printAll(root.right);
}

score 0 · Answer 2 · edited Oct 27 '18 at 04:09

You want to delete a node in a binary search tree. So, basically what you want to do is to make it inaccessible. To do that, you have to nullify the reference to it, i.e, make its parent's corresponding pointer to it as null.

Change this:

if (node.right == null) {
    Node<T> n = node;
    node = null;
    return n;
}

To this:

if (node.right.right == null) {
    Node<T> n = node.right;
    node.right = node.right.left;
    return n;
}

Also you need to take care of the case when the root is the maximum element of the tree. So, if you have some reference to the root of BST, add this case before the above case:

if (node.right == null) {
    Node<T> n = node;
    referenceToTheRootOfBST = node.left;
    return n;
}

If you don't have a reference to the root of the BST, what you can do is deep copy the left node of the root and then remove the left node. So, the above case changes to:

if (node.right == null) {
    Node<T> n = node;
    //I'll assume you don't call this function if root is the only element.
    //if root is the only element.If that's the case, then just make the 
    //root null before calling this function.
    Node<T> leftNode = node.left;
    node.value = leftNode.value;
    node.left = leftNode.left;
    node.right = leftNode.right;
    return n;
}

Another simple way to handle the case that root is the maximum element is to check it before actually calling this function. Simply check if root has a right node, and if it doesn't have it, reallocate the root reference.

Java: Binary Search Tree

2 Answers2