Recursive Binary Search Tree Deletion

Question

Note: I've included the code for the insert in case that is where my error lies.

I'm having trouble removing nodes in my binary search tree. I ran this through eclipse and the node's "pointers" seem to be getting reassigned, but as soon as I exit my recursive method it goes back to the way the node was.

I may be misunderstanding how java is passing the tree nodes between methods.

public abstract class BinaryTree<E> implements Iterable<E> {

    protected class Node<T> {

        protected Node(T data) {
            this.data = data;
        }

        protected T data;
        protected Node<T> left;
        protected Node<T> right;
    }

    public abstract void insert(E data);
    public abstract void remove(E data);
    public abstract boolean search(E data);

    protected Node<E> root;
}

import java.util.Iterator;

public class BinarySearchTree<E extends Comparable<? super E>> extends BinaryTree<E> {

    private Node<E> findIOP(Node<E> curr) {

        curr = curr.left;

        while (curr.right != null) {
            curr = curr.right;
        }

        return curr;
    }

public Iterator<E> iterator() {

    return null;
}

public static void remove(E data) {

    if (root != null){

         if (data.compareTo(root.data) == 0) {

            if (root.left == null || root.right == null) {

                root = root.left != null ? root.left : root.right;


            } else {

                Node<E> iop = findIOP(root);
                E temp = root.data;
                root.data = iop.data;
                iop.data = temp;

                if (root.left == iop) {

                    root.left = root.left.left;

                } else {

                    Node<E> curr = root.left;

                    while (curr.right != iop) {
                        curr = curr.right;
                    }
                    curr.right = curr.right.left;
                }
            }

        } else {

             if (data.compareTo(root.data) < 0) {

                remove(root.left ,data);

             } else {

                remove(root.right ,data);

             }
        }

    }
}

private void remove (Node<E> node, E data){

     if (data.compareTo(node.data) == 0) {

        if (node.left == null || node.right == null) {


            if (node.left != null) {
                                    // Problem is either here
                node = node.left;

            } else {
                                    // or here
                node = node.right;
            }


        } else {

            Node<E> iop = findIOP(node);
            E temp = node.data;
            node.data = iop.data;
            iop.data = temp;

            if (node.left == iop) {

                node.left = node.left.left;

            } else {

                Node<E> curr = node.left;

                while (curr.right != iop) {
                    curr = curr.right;
                }
                curr.right = curr.right.left;
            }
        }
    } else {

         if (data.compareTo(node.data) < 0) {

            remove(node.left ,data);

         } else {

            remove(node.right ,data);

         }
    }

}

}

When I insert:

tree.insert(10);
tree.insert(15);
tree.insert(6);
tree.insert(8);
tree.insert(9);

and then

tree.remove(8);

System.out.println(tree.root.left.right.data);

is still 8 instead of 9.

Removal works at the root and pointers are properly reassigned if removing from root.left and root.right.

Any suggestion would be appreciated.

EDIT: I seem to have narrowed down the question. I implemented an iterative version where I make root = curr and change curr.left.right = curr.left.right.right. I notice that this change reflects my root node while when I pass node = root.left.right to my recursive function changing node to node.right does not reflect the changes in the root. Why is this?

Narrowed down some more. Why does node.left = node.left.left make changes to my tree and node = node.left do nothing.

I fixed it by recursively reassigning nodes of the parent as opposed to recursively reassigning the nodes in the child. This is the resulting private and public function.

public void remove(E data) {

    Node<E> curr;

    if (root != null) {
        if (data.compareTo(root.data) == 0) {
            if (root.left == null || root.right == null) {
                root = root.left != null ? root.left : root.right;
            }
            else {
                Node<E> iop = findIOP(root);
                E temp = root.data;
                root.data = iop.data;
                iop.data = temp;
                if (root.left == iop) {
                    root.left = root.left.left;
                }
                else {
                    curr = root.left;
                    while (curr.right != iop) {
                        curr = curr.right;
                    }
                    curr.right = curr.right.left;
                }
            }
        } else if (data.compareTo(root.data) < 0) {
            root.left = remove(data, root.left);
        } else {
            root.right = remove(data, root.right);
        }
    }
}

private Node<E> remove(E data, Node<E> node){

    Node<E> curr;

    if (node != null){
        if (data.compareTo(node.data) == 0) {
            if (node.left == null || node.right == null) {
                node = node.left != null ? node.left : node.right;
                return node;
            } else {

                Node<E> iop = findIOP(node);
                E temp = node.data;
                node.data = iop.data;
                iop.data = temp;
                if (node.left == iop) {
                    node.left = node.left.left;
                    return node;
                } else {
                    curr = node.left;
                    while (curr.right != iop) {
                        curr = curr.right;
                    }
                    curr.right = curr.right.left;
                    return node;
                }
            }
        } else {
            if (data.compareTo(node.data) < 0) {
                node.left = remove(data, node.left);
                if (node.left != null){
                    return node.left;
                }
            } else {
                node.right = remove(data, node.right);
                if (node.right != null){
                    return node.right;
                }
            }
            // if node.left/right not null
            return node;
        }
    }
    // if node = null;
    return node;
}

I'm almost sure the issue is that when you do the assignment you consider that the object is actually copied, while only the reference is. — Alexandru Barbarosie
I figured it was something like that as well. I'm trying to figure out a way around it with my current data structure. I considered passing the parent node as well, but I'd have no idea which direction the parent traveled. I'm currently trying to pass the node and doing the edits to node.left and node.right prior to passing it recursively. — Mateusz Pejko

Turix Turix · Accepted Answer · 2013-12-09T07:02:52

You are indeed right when you say "I may be misunderstanding how java is passing the tree nodes between methods". Consider:

public class Ref {
    public static void main(String args[]) {
        Integer i = new Integer(4);
        passByRef(i);
        System.out.println(i);    // Prints 4.
    }

    static void passByRef(Integer j) {
        j = new Integer(5);
    }
}

Although i is "passed by reference", the reference i itself isn't changed by the method, only the thing that j refers to. Put another way, j is initialized with a copy of the reference i, that is, j initially refers to the same object as i (but crucially is not i). Assigning j to refer to something else has no effect on what i refers to.

To achieve what you want in your search, I suggest you instead return the new reference to the caller. For example, something analogous to the following change:

public class Ref {
    public static void main(String args[]) {
        Integer i = new Integer(4);
        i = passByRef(i);
        System.out.println(i);    // Prints 5.
    }

    static Integer passByRef(Integer j) {
        j = new Integer(5);
        return j;
    }
}

Recursive Binary Search Tree Deletion

1 Answers