Binary search tree class in Java

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.r

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.

StackExchange Code Review Q#126876, answer score: 2