Binary search tree class in Java

Question

I am trying to create a binary search tree class in Java and am wondering how I did. I am fairly confident on most of the methods, but fear I may have messed up the delete method. I know I am reinventing the wheel, but am just creating this for practice. I know that I also should have made the class generic, but again this was for practice and I felt that it was easier to test with primitive ints instead of the Integer wrapper. I mostly want to know if I implemented the find, delete, and insert methods correctly and if there is anything I can do to improve.

TreeNode

package Chapter4;

public class TreeNode {

public TreeNode left;

public TreeNode right;

public TreeNode parent;

private int data;

public TreeNode(int data) {
    this.data = data;
}

public int getData() {
    return data;
}

public void setData(int data) {
    this.data = data;
}

}

Binary Search Tree

package Chapter4;

import java.util.Random;

public class BinarySearchTree {

private TreeNode root;

BinarySearchTree(TreeNode root) {
    this.root = root;
}

public TreeNode insert(int data) {
    return insert(root, data);
}

private TreeNode insert(TreeNode n, int data) {
    if(n == null) {
        return new TreeNode(data);
    }
    if(data <= n.getData()) {
        TreeNode temp = insert(n.left, data);
        n.left = temp;
        temp.parent = n;
    } else {
        TreeNode temp = insert(n.right, data);
        n.right = temp;
        temp.parent = n;
    }
    return n;
}

public TreeNode delete(int data) {
    TreeNode toDelete = find(data);
    if(toDelete == null) {
        return null; //really should throw
    }
    if(toDelete.left == null && toDelete.right == null) { //has no children
        boolean isLeftChild = (toDelete.parent.left == toDelete);
        if(isLeftChild) {
            toDelete.parent.left = null;
        } else {
            toDelete.parent.right = null;
        }
    } else if((toDelete.left != null && toDelete.right == null) || (toDelete.right != null && toDelete.left == null)) {
        //has one child
        boolean hasChildLeft = (toDelete.left != null);
        boolean isLeftChild = (toDelete.parent.left == toDelete);
        if(hasChildLeft) {
            if(isLeftChild) {
                toDelete.parent.left = toDelete.left;
            } else {
                toDelete.parent.right = toDelete.left;
            }
        } else {
            if(isLeftChild) {
                toDelete.parent.left = toDelete.right;
            } else {
                toDelete.parent.right = toDelete.right;
            }
        }
    } else { //has two children
        TreeNode successor = getNextSuccessor(toDelete);
        toDelete.setData(successor.getData());
        boolean successorIsLeft = (successor.parent.left == successor);
        if(successorIsLeft) {
            successor.parent.left = null;
        } else {
            successor.parent.right = null;
        }
    }
    return toDelete;
}

public TreeNode find(int data) {
    return find(data, this.root);
}

private TreeNode find(int data, TreeNode root) {
    if(root == null) {
        return null; //should throw
    }
    if(data == root.getData()) {
        return root;
    }
    if(data < root.getData()) {
        return find(data, root.left);
    } else {
        return find(data, root.right);
    }
}

public TreeNode getRandomNode() {
    return getRandomNode(this.root);
}

private TreeNode getRandomNode(TreeNode n) { //wrote this for practice
    int leftNodes = n.left == null ? 0 : totalNodes(n.left);
    int total = totalNodes(n);
    int random = new Random().nextInt(total);
    if(random < leftNodes) {
        return getRandomNode(n.left);
    } else if(random == leftNodes) {
        return n;
    } else {
        return getRandomNode(n.right);
    }
}

private int totalNodes(TreeNode root) {
    if(root == null) {
        return 0;
    }
    return 1 + totalNodes(root.left) + totalNodes(root.right);
}

public TreeNode getNextSuccessor(TreeNode n) {
    if(n.right != null) {
        return getMinValue(n.right);
    } else {
        TreeNode parent = n.parent;
        while(parent != null && parent.left != n) {
            n = n.parent;
            parent = n.parent;
        }
        return parent;
    }
}

public TreeNode getMinValue(TreeNode n) {
    while(n.left != null) {
        n = n.left;
    }
    return n;
}

}

Answer 1

Leaky Abstraction

I don't like that you've defined your interface to BinarySearchTree in terms of TreeNodes. By allowing TreeNodes to be passed into and returned from the class, your allow clients to manipulate your tree from the outside. What happens if your supplied root node has the left and right branches supplied the wrong way round? What happens if the caller nulls out the parent pointer in the node returned from insert? If you want to provide a method for clients to iterate over the tree, provide an iterator, this question and its feedback might be a good starting point.

Construction

You tree doesn't supply a default constructor. Given the interface, I'd assume that if I pass in NULL as the root, the class would sort itself out. It doesn't, it sets the root to NULL and from that point it silently ignores anything I try to insert in the tree. It would be better to throw an exception to indicate that it isn't supported functionality.

Bug deleting root

When you delete a node you update links, via the parent pointer. If you're deleting the root node, the parent pointer is null. For example, if you delete the root node of a tree that only has children on the right, you run this code:

boolean isLeftChild = (toDelete.parent.left == toDelete);

This crashes, since toDelete(root).parent is null.