Binary search tree implementation (with Node class)

Question

I have implemented the Binary Search Tree in Java and would love to get reviews. I would like to have some comments on multi thread implantation.

Note: Corrected Code is in the Answers

package com.atleyvirdee.myDataStructures.tree.binarytree;
import com.atleyvirdee.myDataStructures.tree.ITree;
import com.atleyvirdee.myDataStructures.tree.ITreeNode;
import com.atleyvirdee.myDataStructures.tree.DFTreeTraverser;
@SuppressWarnings ( {"rawtypes", "unchecked"} )
public class BinaryTree implements ITree {
 private ITreeNode root;
 public DFTreeTraverser treeTraverser = new DFTreeTraverser(root);
 @Override
 public void insert( Comparable data ) {
 root = insert(data, root);
 }
 @Override
 public void remove( Comparable data ) {
 if ( isEmpty() )
 System.out.println("Tree Empty");
 else if ( find(data) == null )
 System.out.println("Sorry " + data + " is not present");
 else {
 root = remove(data, root);
 }
 }
 @Override
 public void removeMin() {
 ITreeNode minimumNode = findMin(root);
 Comparable data = minimumNode.getData();
 remove(data);
 }
 @Override
 public Comparable find( Comparable data ) {
 ITreeNode dataNode = find(data, root);
 return (dataNode != null) ? dataNode.getData() : null;
 }
 @Override
 public Comparable findMin() {
 ITreeNode minimumNode = findMin(root);
 return minimumNode.getData();
 }
 @Override
 public Comparable findMax() {
 ITreeNode maximumNode = findMax(root);
 return maximumNode.getData();
 }
 @Override
 public boolean isEmpty() {
 return root == null ? true : false;
 }
 @Override
 public void makeEmpty() {
 this.root = null;
 }
 protected ITreeNode findMax( ITreeNode node ) {
 while (node.hasRightNode()) {
 node = node.getRightNode();
 }
 return node;
 }
 protected ITreeNode findMin( ITreeNode node ) {
 while (node.hasLeftNode()) {
 node = node.getLeftNode();
 }
 return node;
 }
 protected ITreeNode find( Comparable data, ITreeNode node ) {
 if ( node == null ) return null;
 if ( node.getData().compareTo(data) == 0 ) return node;
 if ( node.getData().compareTo(data) < 0 ) return find(data, node.getRightNode());
 return find(data, node.getLeftNode());
 }
 protected ITreeNode insert( Comparable data, ITreeNode node ) {
 ITreeNode n;
 if ( node == null ) {
 node = new BinaryTreeNode(data);
 } else if ( data.compareTo(node.getData()) < 0 ) {
 n = insert(data, node.getLeftNode());
 node.setLeftNode(n);
 } else if ( data.compareTo(node.getData()) > 0 ) {
 n = insert(data, node.getRightNode());
 node.setRightNode(n);
 } else {
 throw new RuntimeException("Data already in the Tree.");
 }
 return node;
 }
 protected ITreeNode remove( Comparable data, ITreeNode node ) {
 ITreeNode maxInLeftTree, newLeftChild, n;
 if ( node == null ) {
 return null;
 }
 if ( node.getData() == data ) {
 ITreeNode leftChild = node.getLeftNode();
 ITreeNode rightChild = node.getRightNode();
 if ( leftChild == null && rightChild == null ) // BOTH of the Child are null and Value
 // matched.
 return null;
 else if ( leftChild == null ) {
 return rightChild;
 } else if ( rightChild == null ) {
 return leftChild;
 } else {
 maxInLeftTree = findMax(leftChild);
 Comparable value = maxInLeftTree.getData();
 newLeftChild = remove(value, leftChild);
 node.setData(value);
 node.setLeftNode(newLeftChild);
 return node;
 }
 }
 if ( data.compareTo(node.getData()) < 0 ) {
 n = remove(data, node.getLeftNode());
 node.setLeftNode(n);
 } else {
 n = remove(data, node.getRightNode());
 node.setRightNode(n);
 }
 return node;
 }
 @Override
 public DFTreeTraverser getTraverser() {
 treeTraverser.setRoot(root);
 return treeTraverser;
 }
 class BinaryTreeNode implements ITreeNode {
 ITreeNode leftNode = null;
 ITreeNode rightNode = null;
 Comparable data = null;
 public void setLeftNode( ITreeNode leftNode ) {
 this.leftNode = leftNode;
 }
 public void setRightNode( ITreeNode rightNode ) {
 this.rightNode = rightNode;
 }
 @Override
 public ITreeNode getLeftNode() {
 return this.leftNode;
 }
 @Override
 public ITreeNode getRightNode() {
 return this.rightNode;
 }
 @Override
 public Comparable getData() {
 return this.data;
 }
 @Override
 public boolean hasLeftNode() {
 return (this.leftNode != null) ? true : false;
 }
 @Override
 public boolean hasRightNode() {
 return (this.rightNode != null) ? true : false;
 }
 public BinaryTreeNode( Comparable data ) {
 this.data = data;
 }
 @Override
 public String toString() {
 return this.data.toString();
 }
 @Override
 public void setData( Comparable data ) {
 this.data = data;
 }
 }
 @Override
 public int size() {
 return size(root);
 }
 public int size(ITreeNode node) {
 int leftSize = 0,rightSize =0;
 if(node==null)
 return 0;
 if(node.hasLeftNode())
 leftSize = size(node.getLeftNode());
 if(node.hasRightNode())
 rightSize = size(node.getRightNode());
 return leftSize+rightSize+1;
 }
 @Override
 public ITreeNode getRoot() {
 return root;
 }
}

• h.j.k.: I've opted to rollback the question, see: What should I not do when someone answers my question.
• Programmer: Can I write changed code as answer? @h.j.k.
• h.j.k.: There's a "Posting a self-answer." section in the page I linked to, and generally nothing is stopping you from doing so. :)

Answer 1

First things first:

Generics

Your Comparable is missing it. And I suppose your custom classes are all missing it too. That explains why you are @Supress-ing "unchecked" warnings. I'm not sure if the root cause is because you are retro-fitting some older < Java 1.5 implementations or not, but for type safety please use generics. :)

Some other pointers:

@Override
public void insert( Comparable data ) {
 root = insert(data, root);
}

You probably want to update your treeTraverser here when you (potentially) re-assign your root.

---

@Override
public void remove( Comparable data ) {
 if ( isEmpty() )
 System.out.println("Tree Empty");
 else if ( find(data) == null )
 System.out.println("Sorry " + data + " is not present");
 else {
 root = remove(data, root);
 }
}

1. Inconsistent use of braces here, I'll suggest using it throughout.
2. Using System.out to do logging is a poor choice here, as the logging feature should be abstracted away to a logging framework. With that, you can optionally turn on/off messages on a per-level basis (e.g. DEBUG for development, but WARN for production), or even change the formatting.

---

@Override
public void removeMin() {
 ITreeNode minimumNode = findMin(root);
 Comparable data = minimumNode.getData();
 remove(data);
}
@Override
public Comparable findMin() {
 ITreeNode minimumNode = findMin(root);
 return minimumNode.getData();
}

Duplicated code. You can simply return findMin(root).getData(); from findMin(). Ditto for findMax().

---

protected ITreeNode findMax( ITreeNode node ) {
 while (node.hasRightNode()) {
 node = node.getRightNode();
 }
 return node;
}

Even though this is a very short method, I personally don't favor reassigning method arguments as it may get confusing as to what is being modified/assigned in the future, or for other longer methods. Ditto for findMin(ITreeNode). An alternative for writing the loop above may be:

protected ITreeNode findMax( ITreeNode node ) {
 for (ITreeNode current = node; current.hasRightNode(); 
 current = current.getRightNode()) {
 // empty
 }
 return current;
}

---

protected ITreeNode find( Comparable data, ITreeNode node ) {
 if ( node == null ) return null;
 if ( node.getData().compareTo(data) == 0 ) return node;
 if ( node.getData().compareTo(data) < 0 ) return find(data, node.getRightNode());
 return find(data, node.getLeftNode());
}

I'll suggest saving node.getData().compareTo(data) to a temporary variable and then operate on that:

protected ITreeNode find( Comparable data, ITreeNode node ) {
 if ( node == null ) {
 return null;
 }
 int result = node.getData().compareTo(data);
 return result == 0 ? node : 
 find(data, result < 0 ? node.getRightNode() : node.getLeftNode());
}

---

protected ITreeNode insert( Comparable data, ITreeNode node ) {
 ITreeNode n;
 if ( node == null ) {
 node = new BinaryTreeNode(data);
 } else if ( data.compareTo(node.getData()) < 0 ) {
 n = insert(data, node.getLeftNode());
 node.setLeftNode(n);
 } else if ( data.compareTo(node.getData()) > 0 ) {
 n = insert(data, node.getRightNode());
 node.setRightNode(n);
 } else {
 throw new RuntimeException("Data already in the Tree.");
 }
 return node;
}

1. You don't need the n temporary variable.
2. However, similar to the previous point, you may consider having a temporary variable to store the results of doing the compareTo().
3. Do you really want to throw an Exception for existing data? How about simply returning the Node unmodified?

Putting the suggestions together:

protected ITreeNode insert( Comparable data, ITreeNode node ) {
 if ( node == null ) {
 return new BinaryTreeNode(data);
 }
 int result = data.compareTo(node.getData());
 if ( result < 0 ) {
 node.setLeftNode(insert(data, node.getLeftNode()));
 } else if ( result > 0 ) {
 node.setRightNode(insert(data, node.getRightNode()));
 } else {
 // throw new RuntimeException("Data already in the Tree."); ?
 }
 return node;
}

---

remove() is kind of long to copy here so I'll just mention this: You have one inconsistent usage of braces.

---

@Override
public boolean hasLeftNode() {
 return (this.leftNode != null) ? true : false;
}
@Override
public boolean hasRightNode() {
 return (this.rightNode != null) ? true : false;
}

You don't need the ternary operator here, just do return leftNode != null or return rightNode != null respectively.

---

public int size(ITreeNode node) {
 int leftSize = 0,rightSize =0;
 if(node==null)
 return 0;
 if(node.hasLeftNode())
 leftSize = size(node.getLeftNode());
 if(node.hasRightNode())
 rightSize = size(node.getRightNode());
 return leftSize+rightSize+1;
}

You have pretty consistent and decent whitespacing... until here. You can probably shorten your code as such:

public int size(ITreeNode node) {
 if (node == null) {
 return 0;
 }
 return size(node.getLeftNode()) + size(node.getRightNode()) + 1;
}

• Programmer: Thanks buddy for your feedback. Will check my code for these and then will ask you questions.
• Programmer: I have Implemented the changes on the Code. Traverser root is already being changed in getTranverser Function. @Override public DFTreeTraverser<T> getTraverser() { treeTraverser.setRoot(root); return treeTraverser; }

Answer 2

The only thing I could add is that the main interest of a binary search tree resides in the log(n) height. Without some re-balancing mechanism, in worst case, the tree will behave like a list. You may be interested in taking a look to AVL (they always have an optimal depth), Red-Black, ...

• Programmer: True. Well I have implemented self balancing binary tree in another class. Will share that too for the code review. This was my first tree implementation:)

Answer 3

Following is the corrected code of above Question. Will update this if I get more answers.

package com.atleyvirdee.myDataStructures.tree.binarytree;
import com.atleyvirdee.myDataStructures.tree.ITree;
import com.atleyvirdee.myDataStructures.tree.ITreeNode;
import com.atleyvirdee.myDataStructures.tree.DFTreeTraverser;
public class BinaryTree<T extends Comparable<T>> implements ITree<T> {
 private ITreeNode<T> root;
 public DFTreeTraverser<T> treeTraverser = new DFTreeTraverser<T>(root);
 @Override
 public void insert( T data ) {
 root = insert(data, root);
 }
 @Override
 public void remove( T data ) {
 if ( isEmpty() )
 System.out.println("Tree Empty");
 else if ( find(data) == null )
 System.out.println("Sorry " + data + " is not present");
 else {
 root = remove(data, root);
 }
 }
 @Override
 public void removeMin() {
 ITreeNode<T> minimumNode = findMin(root);
 T data = minimumNode.getData();
 remove(data);
 }
 @Override
 public T find( T data ) {
 ITreeNode<T> dataNode = find(data, root);
 return (dataNode != null) ? dataNode.getData() : null;
 }
 @Override
 public T findMin() {
 return findMin(root).getData();
 }
 @Override
 public T findMax() {
 return findMax(root).getData();
 }
 @Override
 public boolean isEmpty() {
 return root == null ? true : false;
 }
 @Override
 public void makeEmpty() {
 this.root = null;
 }
 protected ITreeNode<T> findMax( ITreeNode<T> node ) {
 ITreeNode<T> current = node;
 while (current.hasRightNode()) {
 current = current.getRightNode();
 }
 return current;
 }
 protected ITreeNode<T> findMin( ITreeNode<T> node ) {
 ITreeNode<T> current = node;
 while (current.hasLeftNode()) {
 current = current.getLeftNode();
 }
 return current;
 }
 protected ITreeNode<T> find( T data, ITreeNode<T> node ) {
 if ( node == null ) return null;
 int result = node.getData().compareTo(data);
 return result == 0 ? node : find(data, result < 0 ? node.getRightNode() : node.getLeftNode());
 }
 protected ITreeNode<T> insert( T data, ITreeNode<T> node ) {
 ITreeNode<T> n;
 if ( node == null ) {
 node = new BinaryTreeNode<T>(data);
 return node;
 }
 int result = data.compareTo(node.getData());
 if ( result < 0 ) {
 n = insert(data, node.getLeftNode());
 node.setLeftNode(n);
 } else if ( result > 0 ) {
 n = insert(data, node.getRightNode());
 node.setRightNode(n);
 } else {
 throw new RuntimeException("Data already in the Tree.");
 }
 return node;
 }
 protected ITreeNode<T> remove( T data, ITreeNode<T> node ) {
 ITreeNode<T> maxInLeftTree, newLeftChild, n;
 if ( node == null ) {
 return null;
 }
 if ( node.getData() == data ) {
 ITreeNode<T> leftChild = node.getLeftNode();
 ITreeNode<T> rightChild = node.getRightNode();
 if ( leftChild == null && rightChild == null ) // BOTH of the Child are null and Value
 // matched.
 return null;
 else if ( leftChild == null ) {
 return rightChild;
 } else if ( rightChild == null ) {
 return leftChild;
 } else {
 maxInLeftTree = findMax(leftChild);
 T value = maxInLeftTree.getData();
 newLeftChild = remove(value, leftChild);
 node.setData(value);
 node.setLeftNode(newLeftChild);
 return node;
 }
 }
 if ( data.compareTo(node.getData()) < 0 ) {
 n = remove(data, node.getLeftNode());
 node.setLeftNode(n);
 } else {
 n = remove(data, node.getRightNode());
 node.setRightNode(n);
 }
 return node;
 }
 @Override
 public DFTreeTraverser<T> getTraverser() {
 treeTraverser.setRoot(root);
 return treeTraverser;
 }
 class BinaryTreeNode<E extends Comparable<E>> implements ITreeNode<E> {
 ITreeNode<E> leftNode = null;
 ITreeNode<E> rightNode = null;
 E data = null;
 public void setLeftNode( ITreeNode<E> leftNode ) {
 this.leftNode = leftNode;
 }
 public void setRightNode( ITreeNode<E> rightNode ) {
 this.rightNode = rightNode;
 }
 @Override
 public ITreeNode<E> getLeftNode() {
 return this.leftNode;
 }
 @Override
 public ITreeNode<E> getRightNode() {
 return this.rightNode;
 }
 @Override
 public E getData() {
 return this.data;
 }
 @Override
 public boolean hasLeftNode() {
 return this.leftNode != null;
 }
 @Override
 public boolean hasRightNode() {
 return this.rightNode != null;
 }
 public BinaryTreeNode( E data ) {
 this.data = data;
 }
 @Override
 public String toString() {
 return this.data.toString();
 }
 @Override
 public void setData( E data ) {
 this.data = data;
 }
 }
 @Override
 public int size() {
 return size(root);
 }
 public int size( ITreeNode<T> node ) {
 if ( node == null ) return 0;
 return size(node.getLeftNode()) + size(node.getRightNode()) + 1;
 }
 @Override
 public ITreeNode<T> getRoot() {
 return root;
 }
}