Binary Search Tree Implementation in Java

Question

Looking for critiques on my BST implementation, particularly to check if I'm building the common operational methods and traversal algorithms properly. Code has been lightly tested, and I've tried to make it as legible as possible.

public class BinarySearchTree<T extends Comparable<T>> { private BinaryTreeNode<T> root; private int size; /** * Recursively inserts an element into the tree. * @param value value to insert. * @return true if insertion was successful, false if otherwise. */ public boolean insert(T value) { try { this.root = insert(this.root, value); this.size++; return true; } catch(Exception e) { return false; } } private BinaryTreeNode<T> insert(BinaryTreeNode<T> node, T value) { if(node == null) { return new BinaryTreeNode(value); } int result = value.compareTo(node.getData()); if(result <= 0) { node.setLeft(insert(node.getLeft(), value)); } else { node.setRight(insert(node.getRight(), value)); } return node; } /** * Recursively removes a specified element from the tree. * @param value value to remove. * @return true if removal was successful, false if otherwise. */ public boolean remove(T value) { try { this.root = remove(this.root, value); this.size--; return true; } catch(Exception e) { return false; } } private BinaryTreeNode<T> remove(BinaryTreeNode<T> node, T value) { if(!isEmpty()) { while(node != null) { int result = value.compareTo(node.getData()); if (result == 0) { if (node.getLeft() != null && node.getRight() != null) { node = findMin(node.getRight()); remove(node.getRight(), node.getData()); } else { node = (node.getLeft() != null) ? node.getLeft() : node.getRight(); } } else if (result < 0) { node = node.getLeft(); } else { node = node.getRight(); } } } return node; } /** * Recursively finds a specified value within the tree, if it exists. * @param value value to find. * @return node containing the search value, null if value cannot be found. */ public BinaryTreeNode<T> find(T value) { return find(this.root, value); } private BinaryTreeNode<T> find(BinaryTreeNode<T> node, T value) { if(node == null) { return node; } int result = value.compareTo(node.getData()); if(result == 0) { return node; } else if(result < 0) { return find(node.getLeft(), value); } else { return find(node.getRight(), value); } } /** * Returns a node containing the minimum value within tree, if it exists. * @return value containing minimum-value node, null if value cannot be found. */ public BinaryTreeNode<T> findMin() { return findMin(this.root); } private BinaryTreeNode<T> findMin(BinaryTreeNode<T> node) { if(!isEmpty()) { while(node.getLeft() != null) { node = node.getLeft(); } return node; } return null; } /** * Returns a node containing the maximum value within the tree, if it exists. * @return value containing the maximum-value node, null if value cannot be found. */ public BinaryTreeNode<T> findMax() { return findMax(this.root); } private BinaryTreeNode<T> findMax(BinaryTreeNode<T> node) { if(!isEmpty()) { while(node.getRight() != null) { node = node.getRight(); } return node; } return null; } /** * Recursively traverses the tree using In-Order Traversal. * @return a Doubly-Linked List representing the traversal order. */ public ArrayList<BinaryTreeNode<T>> traverseInOrder() { return traverseInOrder(this.root, new ArrayList()); } private ArrayList<BinaryTreeNode<T>> traverseInOrder(BinaryTreeNode<T> node, ArrayList<BinaryTreeNode<T>> order) { if(node == null) { return order; } traverseInOrder(node.getLeft(), order); order.add(node); traverseInOrder(node.getRight(), order); return order; } /** * Recursively traverses the tree using Pre-Order traversal. * @return a Doubly-Linked List representing the traversal order. */ public ArrayList<BinaryTreeNode<T>> traversePreOrder() { return traversePreOrder(this.root, new ArrayList()); } private ArrayList<BinaryTreeNode<T>> traversePreOrder(BinaryTreeNode<T> node, ArrayList<BinaryTreeNode<T>> order) { if(node == null) { return order; } order.add(node); traversePreOrder(node.getLeft(), order); traversePreOrder(node.getRight(), order); return order; } /** * Recursively traverses the tree using Post-Order traversal. * @return a Doubly-Linked List representing the traversal order. */ public ArrayList<BinaryTreeNode<T>> traversePostOrder() { return traversePostOrder(this.root, new ArrayList<BinaryTreeNode<T>>()); } private ArrayList<BinaryTreeNode<T>> traversePostOrder(BinaryTreeNode<T> node, ArrayList<BinaryTreeNode<T>> order) { if(node == null) { return order; } traversePostOrder(node.getLeft(), order); traversePostOrder(node.getRight(), order); order.add(node); return order; } /** * Determines whether or not a value exists within the tree, using Depth-First Search. * Uses a wrapper method to initialize objects required for search traversal. * @param data value to search for. * @return true if the value exists within the tree, false if otherwise. */ public boolean depthFirstSearch(T data) { if(getSize() <= 0) { return false; } Stack<BinaryTreeNode<T>> stack = new Stack(); stack.push(this.root); return depthFirstSearch(stack, data); } private boolean depthFirstSearch(Stack<BinaryTreeNode<T>> stack, T data) { HashMap<BinaryTreeNode<T>, VisitStatus> visited = new HashMap(); while(!stack.isEmpty()) { BinaryTreeNode<T> current = stack.pop(); visited.put(current, VisitStatus.Visiting); if(current.getData().equals(data)) { return true; } if(current.getRight() != null) { if(visited.containsKey(current.getRight())) { if(visited.get(current.getRight()).equals(VisitStatus.Unvisited)) { stack.push(current.getRight()); } } else { stack.push(current.getRight()); } } if(current.getLeft() != null) { if(visited.containsKey(current.getLeft())) { if(visited.get(current.getLeft()).equals(VisitStatus.Unvisited)) { stack.push(current.getLeft()); } } else { stack.push(current.getLeft()); } } visited.put(current, VisitStatus.Visited); } return false; } /** * Determines whether or not a value exists within the tree, using Breadth-First Search. * Uses a wrapper method to initialize objects required for search traversal. * @param data value to search for. * @return true if the value exists within the tree, false if otherwise. */ public boolean breadthFirstSearch(T data) { if(getSize() <= 0) { return false; } LinkedList<BinaryTreeNode<T>> queue = new LinkedList(); queue.addLast(this.root); return breadthFirstSearch(queue, data); } public boolean breadthFirstSearch(Queue<BinaryTreeNode<T>> queue, T data) { HashMap<BinaryTreeNode<T>, VisitStatus> visited = new HashMap(); while(!queue.isEmpty()) { BinaryTreeNode<T> current = queue.remove(); visited.put(current, VisitStatus.Visiting); if(current.getData().equals(data)) { return true; } if(current.getLeft() != null) { if(visited.containsKey(current.getLeft())) { if(visited.get(current.getLeft()).equals(VisitStatus.Unvisited)) { queue.add(current.getLeft()); } } else { queue.add(current.getLeft()); } } if(current.getRight() != null) { if(visited.containsKey(current.getRight())) { if(visited.get(current.getRight()).equals(VisitStatus.Unvisited)) { queue.add(current.getRight()); } } else { queue.add(current.getRight()); } } } return false; } /** * Gets and returns the root of the tree. * @return a node representing the root of the tree. */ public BinaryTreeNode<T> getRoot() { return this.root; } /** * Returns an array representing the current tree. * @param clazz underlying tree data type. * @return an array containing properly-ordered tree values. */ public T[] toArray(Class<T> clazz) { return toArray((T[])Array.newInstance(clazz, this.size), 0, this.root); } private T[] toArray(T[] arr, int i, BinaryTreeNode<T> node) { if(node == null || i > this.size - 1) { return arr; } arr[i] = node.getData(); arr = (node.getLeft() != null) ? toArray(arr, (2 * i) + 1, node.getLeft()) : arr; arr = (node.getRight() != null) ? toArray(arr, (2 * i) + 2, node.getRight()) : arr; return arr; } /** * Builds a tree from a specified array. * @param arr array of source values. */ public void toTree(T[] arr) { for(int i = 0; i < arr.length; i++) { insert(arr[i]); } } /** * Determines whether or not the tree is empty. * @return true if tree is empty, false if otherwise. */ public boolean isEmpty() { if(this.root == null) { return true; } return false; } /** * Returns the current size of the tree. * @return an integer representing the size of the tree. */ public int getSize() { return this.size; } } 

BinaryTreeNode class:

public class BinaryTreeNode<T> extends TreeNode<T> { private BinaryTreeNode<T> left; private BinaryTreeNode<T> right; public BinaryTreeNode() {} public BinaryTreeNode(T data) { super(data); } public BinaryTreeNode(BinaryTreeNodeBuilder<T> builder) { this.data = builder.data; this.left = builder.left; this.right = builder.right; } public BinaryTreeNode<T> getLeft() { return left; } public void setLeft(BinaryTreeNode<T> left) { this.left = left; } public BinaryTreeNode<T> getRight() { return right; } public void setRight(BinaryTreeNode<T> right) { this.right = right; } public static class BinaryTreeNodeBuilder<T> { private T data; private BinaryTreeNode<T> left; private BinaryTreeNode<T> right; public BinaryTreeNodeBuilder<T> data(T data) { this.data = data; return this; } public BinaryTreeNodeBuilder<T> left(BinaryTreeNode<T> left) { this.left = left; return this; } public BinaryTreeNodeBuilder<T> right(BinaryTreeNode<T> right) { this.right = right; return this; } } } 

TreeNode class:

public class TreeNode<T> { protected T data; public TreeNode() {} public TreeNode(T data) { this.data = data; } public T getData() { return data; } public void setData(T data) { this.data = data; } } 

VisitStatus enum:

public enum VisitStatus { Unvisited, Visiting, Visited } 

Answer 1

Enum members

They should be uppercase. They're constants.

enum VisitStatus { UNVISITED, VISITING, VISITED } 

TreeNode

This is not a useful abstraction. Inheritance should be avoided unless there's a very good reason to use it. Favour composition. In this case, just consolidate TreeNode into BinaryTreeNode.

Builder pattern

Your code doesn't actually use your builder, but I'll comment on it anyway. Having a public constructor which takes a builder is unusual:

public BinaryTreeNode(BinaryTreeNodeBuilder<T> builder) { 

I would make this private. To then instantiate the buildable, it's much more common to have a build method on your builder:

@Override public BinaryTreeNode<T> build() { return new BinaryTreeNode<>(data, left, right); } 

Optionally, you can have your builder implement a builder interface, such as org.apache.commons.lang3.builder.Builder, or define your own like so:

interface Builder<T> { T build(); } 

See Item 2 in Josh Bloch's Effective Java for a good example of the pattern. In your case you don't gain much from having a builder as your node only has 3 properties.

Aim for immutability

You have a setData method which is never used. Conceptually does it make sense to change a node's data once it's been created? Probably not. Remove the setter and declare data as final. The fewer fields that can change in a class, the easier that class becomes to work with. If a class is completely immutable, you get benefits like thread-safety without having to synchronize. If a class must be mutable - for example, for performance reasons - then make it as immutable as possible.

Don't blanket catch exceptions

In some methods, you catch all exceptions and return false to indicate a failure:

try { this.root = insert(this.root, value); this.size++; return true; } catch(Exception e) { return false; } 

There's any number of low-level problems you could be masking here that have nothing to do with your code, for example an OutOfMemoryError. Enough has been said about this already. See this question, for example.

Don't repeat yourself

You might have been able to observe that your private findMin and findMax methods have almost identical implementations. You can consolidate them into one method which takes a function as an additional parameter:

private BinaryTreeNode<T> findExtreme(BinaryTreeNode<T> node, final Function<BinaryTreeNode<T>, BinaryTreeNode<T>> getter) { if(!isEmpty()) { while(getter.apply(node) != null) { node = getter.apply(node); } return node; } return null; } 

Then you can change your public methods to:

return findExtreme(this.root, BinaryTreeNode::getLeft); 

and

return findExtreme(this.root, BinaryTreeNode::getRight); 

Prefer abstractions

There are numerous places where you return or expect an ArrayList. This is needlessly restrictive. It is preferable to use more abstract concepts, i.e. interfaces such as List or Collection, because it allows you to change the implementation later - perhaps to improve performance - without breaking the code of clients who call your methods.

Use type inference to your advantage

Here, for example, you can get away with using the diamond operator to remove the need to repeat the type twice:

public ArrayList<BinaryTreeNode<T>> traversePostOrder() { return traversePostOrder(this.root, new ArrayList<BinaryTreeNode<T>>()); } 

The ArrayList instantiation can simply become

new ArrayList<>() 

Don't use raw types

Here you are using the raw type of HashMap. You should never need to use raw types after Java 1.5.

HashMap<BinaryTreeNode<T>, VisitStatus> visited = new HashMap(); 

Once again, you can use the diamond operator to infer the correct type from the left-hand side.

if(condition) { return true; } else { return false; }

If you ever find yourself writing something in the above format - and you do:

public boolean isEmpty() { if(this.root == null) { return true; } return false; } 

Then you can always simplify it to simply return condition;. In your case:

return this.root == null; 

This is little quirk of boolean logic that beginners often don't spot. I know it took me a while to get it. Once you do, you'll cringe any time you see someone write it the way you have!

---

I'm not an algorithms guy so I haven't commented on correctness or efficiency.