Generic Binary Search Tree Implementation in Java

Question

There is an implementation of Binary Search Tree. This is kind of based on Set Theory that duplicates are not allowed but an attempt to adding the same node twice will replace the older node.

BSTNode Class:

package nodes.treeNodes.binaryTreesNode.bstNode; import java.util.Iterator; import java.util.LinkedList; import java.util.List; public class BSTNode<T> { private BSTNode<T> parent; private BSTNode<T> leftChild; private BSTNode<T> rightChild; private T data; public BSTNode(T data) { this(null, null, null, data); } public BSTNode(BSTNode<T> parent, BSTNode<T> leftChild, BSTNode<T> rightChild, T data) { this.parent = parent; this.leftChild = leftChild; this.rightChild = rightChild; this.data = data; } public BSTNode <T> getParent() { return parent; } public void setParent(BSTNode <T> parent) { this.parent = parent; } public BSTNode <T> getLeftChild() { return leftChild; } public void setLeftChild(BSTNode <T> leftChild) { this.leftChild = leftChild; } public BSTNode <T> getRightChild() { return rightChild; } public void setRightChild(BSTNode <T> rightChild) { this.rightChild = rightChild; } public T getData() { return data; } public void setData(T data) { this.data = data; } public void removeChild(BSTNode<T> child) { if(child == null) return; if(this.getRightChild() == child) { this.setRightChild(null); return; } if(this.getLeftChild() == child) this.setLeftChild(null); } public Iterator<BSTNode> children() { List<BSTNode> childList = new LinkedList<>(); if(this.leftChild != null) childList.add(leftChild); if(this.rightChild != null) childList.add(rightChild); return childList.iterator(); } } 

BST Class:

package trees.binaryTrees.bst; import nodes.treeNodes.binaryTreesNode.bstNode.BSTNode; import java.util.Iterator; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.concurrent.ConcurrentLinkedQueue; public class BST<T extends Comparable<T>> { private BSTNode<T> root; private int size; public BST() {} private BSTNode<T> root() { return root; } private void addRoot(T data) throws Exception { if(root != null) throw new Exception("Root exists is the tree."); root = new BSTNode <>(data); size++; } public void add(T data) throws Exception { BSTNode<T> node = find(data); if (node == null) addRoot(data); else if (node.getData().compareTo(data) > 0) addLeft(node, data); else if (node.getData().compareTo(data) < 0) addRight(node, data); else node.setData(data); } private void addLeft(BSTNode<T> parent, T data) { BSTNode<T> left = new BSTNode <>(data); parent.setLeftChild(left); left.setParent(parent); size++; } private void addRight(BSTNode<T> parent, T data) { BSTNode<T> right = new BSTNode <>(data); parent.setRightChild(right); right.setParent(parent); size++; } public void remove(T data) { BSTNode<T> node = find(data); if(node == null || !node.getData().equals(data)) return; remove(node); } private BSTNode<T> remove(BSTNode<T> node) { if (isLeaf(node)) { BSTNode<T> parent = node.getParent(); if (parent == null) root = null; else parent.removeChild(node); size--; return parent; } BSTNode<T> descendant = descendant(node); promoteDescendant(node, descendant); return remove(descendant); } private void promoteDescendant(BSTNode<T> parent, BSTNode<T> descendant) { parent.setData(descendant.getData()); } private BSTNode<T> descendant(BSTNode<T> parent) { BSTNode<T> child = parent.getLeftChild(); if (child != null) { while (child.getRightChild() != null) child = child.getRightChild(); return child; } child = parent.getRightChild(); if (child != null) { while (child.getLeftChild() != null) child = child.getLeftChild(); return child; } return child; } public T get(T data) { BSTNode<T> node = find(data); if(node == null || !node.getData().equals(data)) return null; return node.getData(); } public boolean contains(T data) { BSTNode<T> node = find(data); if(node == null || !node.getData().equals(data)) return false; return true; } private BSTNode<T> find(T data) { if(root() == null) return null; return findRecursively(root(), data); } private BSTNode<T> findRecursively(BSTNode<T> parent, T data) { int comparison = data.compareTo(parent.getData()); if(comparison == 0) return parent; else if(comparison < 0 && parent.getLeftChild() != null) return findRecursively(parent.getLeftChild(), data); else if(comparison > 0 && parent.getRightChild() != null) return findRecursively(parent.getRightChild(), data); return parent; } public boolean isEmpty() { return size() == 0; } public int size() { return size; } private BSTNode<T> parent(BSTNode<T> child) { return child.getParent(); } private boolean isInternal(BSTNode<T> node) { return node.children().hasNext(); } private boolean isLeaf(BSTNode<T> node) { return !isInternal(node); } private int depth(BSTNode<T> node) { if(isLeaf(node)) return 0; return depth(node.getParent()) + 1; } private int height(BSTNode<T> node) { if(isLeaf(node)) return 0; int maxHeight = 0; Iterator<BSTNode> children = node.children(); while (children.hasNext()) { int height = height(children.next()); if(height > maxHeight) maxHeight = height; } return maxHeight + 1; } public int height() { if(root == null) return -1; return height(root); } public List<T> preOrder() { List<T> list = new LinkedList<>(); preOrder(root, list); return list; } private void preOrder(BSTNode<T> node, List<T> list) { if(node == null) return; list.add(node.getData()); Iterator<BSTNode> children = node.children(); while (children.hasNext()) { preOrder(children.next(), list); } } public List<T> postOrder() { List<T> list = new LinkedList <>(); postOrder(root(), list); return list; } private void postOrder(BSTNode<T> node, List<T> list) { if(node == null) return; Iterator<BSTNode> children = node.children(); while (children.hasNext()) { postOrder(children.next(), list); } list.add(node.getData()); } public List<T> levelOrder() { List<T> nodeList = new LinkedList <>(); if(root() == null) return nodeList; Queue<BSTNode> nodeQueue = new ConcurrentLinkedQueue <>(); try { nodeList.add(root().getData()); nodeQueue.add(root()); while (!nodeQueue.isEmpty()) { BSTNode<T> node = nodeQueue.poll(); Iterator<BSTNode> nodeItr = node.children(); while (nodeItr.hasNext()) { BSTNode<T> treeNode = nodeItr.next(); nodeQueue.add(treeNode); nodeList.add(treeNode.getData()); } } } catch (Exception ex) { System.out.println(ex.getMessage()); } return nodeList; } public List<T> inOrder() { List<T> answer = new LinkedList <>(); inOrder(root(), answer); return answer; } private void inOrder(BSTNode<T> node, List<T> list) { if (node == null) return; inOrder(node.getLeftChild(), list); list.add(node.getData()); inOrder(node.getRightChild(), list); } @Override public String toString() { return inOrder().toString(); } } 

Answer 1

Don't throw Exception

It's recommended to throw a specific type of exception, and avoid the overly general Exception.

Think twice before using checked exceptions

The addRoot method throws Exception when a root node already exists in the tree. This is a checked exception, which means that callers must catch it and handle it. This method is only called by add, and it doesn't handle it, instead it declares to throw as well. Users of this class may wonder: "why do I have to catch this exception"? Or, "what can go wrong while adding a node"? In fact, you won't be able to give a good answer to that question. Using the public API of this class, an exception will never be thrown. The only way the program might set root twice is if you have some mistake in the implementation. In such case, a more appropriate exception type would be IllegalStateException. That's a runtime exception, and users of the class won't have to handle it.

Hide implementation details

From the posted code, I don't see a reason for the BSTNode class to be publicly visible. If that's the case, then it would be better to make it a private static inner class of BST, to hide this implementation detail from users of BST.

Remove pointless get method

The T get(T data) method returns null if data is not found, or else data. This is an unusual feature of a BST. Whatever this could be useful for, it could be implemented in terms of contains.

Use appropriate data types

levelOrder uses a ConcurrentLinkedQueue for its queue. Why not simply a LinkedList or Deque?

Also, why does children() return an Iterator instead of a List? With a List, iterating over the children would be more compact to implement.