Problem
I wrote my own version of a search binary tree in Java. Could someone kindly review it?
public class Tree {
private Node root;
public Node find(int id) {
Node current = root;
while(current != null) {
if (current.getId() == id)
// Node found
return current;
current = goNextChild(current, id);
}
return current;
}
public void insert(int id, String name) {
Node node = new Node(id, name);
if (root == null)
root = node;
else {
Node current = root;
while(current != null) {
if (current.getId() == id) {
// If present, just change information of the current node
current.setId(id);
current.setName(name);
return;
}
else if (current.getId() < id) {
// Go to the right child
if (current.getRightChild() == null) {
// If the right child is not present set the new node
current.setRightChild(node);
return;
}
else {
current = current.getRightChild();
}
}
else if (current.getId() > id) {
// go to the left child
if (current.getLeftChild() == null) {
// If the left child is not present set the new node
current.setLeftChild(node);
return;
}
else {
current = current.getLeftChild();
}
}
}
}
}
public void delete(int id) {
Node delNode = find(id);
Node parent = findParent(delNode);
if((delNode.getLeftChild() == null)
&& (delNode.getRightChild() == null)) {
// Delete node with no children
if (delNode == root)
root = null;
else if(parent.getLeftChild() == delNode)
parent.setLeftChild(null);
else if(parent.getRightChild() == delNode)
parent.setRightChild(null);
}
else if(delNode.getLeftChild() == null) {
// Delete node with one child
if (delNode == root)
root = delNode.getRightChild();
else if(parent.getLeftChild() == delNode)
parent.setLeftChild(delNode.getRightChild());
else if(parent.getRightChild() == delNode)
parent.setRightChild(delNode.getRightChild());
}
else {
// Delete node with two children
Node successor = produceSuccessor(delNode);
if (delNode == root)
root = successor;
else if(parent.getLeftChild() == delNode)
parent.setLeftChild(successor);
else if(parent.getRightChild() == delNode)
parent.setRightChild(successor);
}
}
public Node findParent(Node node) {
Node current = root;
while(current != null) {
if (isParent(current, node))
return current;
current = goNextChild(current, node.getId());
}
return null;
}
public void traverse() {
inOrderTraverse(root);
}
private void inOrderTraverse(Node node) {
if (node != null) {
inOrderTraverse(node.getLeftChild());
System.out.print(node.getId() + " ");
inOrderTraverse(node.getRightChild());
}
}
private Node produceSuccessor(Node node) {
// Go to the right only once
Node successor = node.getRightChild();
if (successor.getLeftChild() == null) {
// If the right child has no left child, then
// Some re-connections are needed
successor.setLeftChild(node.getLeftChild());
}
else {
// Go to the left multiple times
while (successor.getLeftChild() != null) {
successor = successor.getLeftChild();
}
findParent(successor).setLeftChild(null);
successor.setLeftChild(node.getLeftChild());
successor.setRightChild(node.getRightChild());
}
return successor;
}
private Node goNextChild(Node node, int id) {
if (node.getId() < id)
// Go to the right child
return node.getRightChild();
else
// go to the left child
return node.getLeftChild();
}
private boolean isParent(Node parent, Node child) {
if (parent == null || child == null)
return false;
if (parent.getLeftChild() != null &&
parent.getLeftChild().getId() == child.getId())
return true; // child is left node
if (parent.getRightChild() != null &&
parent.getRightChild().getId() == child.getId())
return true; // child is right node
return false;
}
}
public class TreeData {
private int id;
private String name;
public TreeData(int id, String name) {
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
}
public class Node {
private TreeData data; // Don't return this, see Demeter law
private Node leftChild;
private Node rightChild;
public Node(int id, String name) {
data = new TreeData(id, name);
}
public Node getLeftChild() {
return leftChild;
}
public void setLeftChild(Node leftChild) {
this.leftChild = leftChild;
}
public Node getRightChild() {
return rightChild;
}
public void setRightChild(Node rightChild) {
this.rightChild = rightChild;
}
public int getId() {
return data.getId();
}
public void setId(int id) {
data.setId(id);
}
public String getName() {
return data.getName();
}
public void setName(String name) {
data.setName(name);;
}
}
public class App {
public static void main(String[] args) {
Tree tree = new Tree();
tree.insert(3, "Albert");
tree.insert(1, "Roby");
tree.insert(4, "Jack");
tree.insert(8, "Ron");
tree.insert(11, "Black");
tree.insert(9, "Bob");
tree.insert(7, "Bongo");
tree.traverse();
System.out.println("");
tree.delete(4);
tree.traverse();
System.out.println("");
tree.delete(8);
tree.traverse();
System.out.println("");
tree.delete(3);
tree.traverse();
System.out.println("");
tree.delete(1);
tree.traverse();
System.out.println("");
tree.delete(7);
tree.traverse();
System.out.println("");
tree.delete(9);
tree.traverse();
System.out.println("");
tree.delete(11);
tree.traverse();
}
}
Solution
Design
- I highly recommend that you create a Tree interface that can be implemented by a BinarySearchTree class. Take your insert, delete, find, etc. methods and declare them over there. Suppose you decide to create a Red-Black tree, then you could create a RedBlackTree class which implements the same interface. This makes swapping out implementations very easy! Here’s a good link to read: Why would a programmer want to separate implementation from interface?
- Why do you need the TreeData class? If you ask yourself “What is a node in a tree and what does it do?”, then your POJO should reflect that answer. In this case, a tree node has a key, a value (or some piece of data), a left child, and a right child. Why shouldn’t the Node represent this itself? Sure, you don’t need to expose setter methods for each attribute, but by adding getter methods on Node, you’re still exposing the attributes indirectly.
Correctness
- Take a look at your find() method. Currently, if the Node you’re searching for doesn’t exist, you return the root of the tree. Is that really what you want to do? I would either return null, or take a look at the Optional documentation (would recommend going this route as it’s a good way to help avoid null pointer exceptions!).
Minor Notes
- Make variables final when possible. It’ll make your code less error-prone and is just general good-practice.
- Take a look at your ‘if-else’ statements, and you’ll notice you’ve got some cases where you have ‘if, else if, else if’. I highly recommend following a conventional ‘if, else if, else’ pattern to prevent bugs in the code. If you need to, add some documentation to clarify the branches.
Insert:
Your insert operation is a bit overcomplicated.
- Your last outer
else ifis redundant a plainelsewould suffice. - Your nested
ifs are unnecessary IMO a more readable way would be to keep track of the parent and after the loop terminates add the new node.
Delete:
You have to much code repetition for example you use this several times
if (delNode == root)
root = delNode.getRightChild();
else if(parent.getLeftChild() == delNode)
parent.setLeftChild(delNode.getRightChild());
else if(parent.getRightChild() == delNode)
parent.setRightChild(delNode.getRightChild());
You should abstract this into a function.
This first if:
if((delNode.getLeftChild() == null)
&& (delNode.getRightChild() == null))
Can be change to this:
if(delNode.getRightChild() == null)
And put the same code as the fist if changing getRightChild() to getLeftChild(). You code would end up in the third case even when delNode.getRightChild() is null and delNode.getLeftChild() is not.
Finally you are traversing the tree 2 times for finding the parent and the node, which even though it doesn’t change the asymptotic running time its unnecessary.
Node class
I would make your class nested. Also Node is an implementation detail so it should be private. I would omit the setters method as well because in this particular case you wont need to do any additional operations or validations.
Comments
Your comments are completely worthless. You should comment your code only if it does help or for API documentation. But in general you should let the code speak for itself.
Additional notes:
Apart from what TheDesertMonk said you can use generics for your map.
There are more things that can be improved but I need to sleep ;).