Pastable version of first BST

<pre class='prettyprint' language='java'>package BST;
import exceptions.DuplicateItemException;

// Here I implement a very basic binary search tree, which
// checks for duplicate items. The tree is not balanced,
// so it is possible for an instance of this class to
// degenerate into a linked list (thus rendering any
// operations that would normally be logarithmic in regards
// to time would be linear. 
public class BST&lt;E&gt; 
{
	// Node is a statically-nested class. As such, it doesn't
	// have access to any other member of the enclosing class,
	// BST. 
	@SuppressWarnings(&quot;unchecked&quot;)
	private static class Node&lt;Comparable&gt;
	{
		public Node left;
		public Node right;
		public Comparable data; 
		
		public Node(Comparable data, Node left, Node right)
		{
			this.left = null;
			this.right = null;
			this.data = data;
		}
	}
	
	private Node&lt;Comparable&gt; root; 
	private int count;
	
	public BST()
	{
		root = null;
		count = 0;
	}
	
	public boolean isEmpty()
	{
		return root == null;
	}
	
	// This contains() method only delegates work
	// to the recusrive contains() method. 
	public boolean contains (Comparable data)
	{
		return contains(root, data);
	}
	
	@SuppressWarnings(&quot;unchecked&quot;)
	private boolean contains (Node ref, Comparable data)
	{
		if (ref == null)
			return false;
		else if (data.compareTo(ref.data) == 0)
			return true;
		else if (data.compareTo(ref.data) &lt; 0)
			return contains (ref.left, data);
		else if (data.compareTo(ref.data) &gt; 0)
			return contains (ref.right, data);
		else
			return false; 
	}
	
	// This add() method only delegates the work of
	// actually inserting an item to the insert()
	// method.
	@SuppressWarnings(&quot;unchecked&quot;)
	public void add (Comparable data) throws DuplicateItemException
	{
		root = insert(root, data);
	}
	
	private Node insert (Node current, Comparable data) throws DuplicateItemException
	{
		if(current == null)
			current = new Node(data, null, null);
		else if (data.compareTo(current.data) &lt; 0)
			current.left = insert (current.left, data);
		else if (data.compareTo(current.data) &gt; 0)
			current.right = insert (current.right, data);
		else if (data.compareTo(current.data) == 0)
			throw new DuplicateItemException (data.toString());
		count++;
		return current;
	}
	
	// This method just delegates the work of
	// traversing the tree to the print()
	// method.
	public void printAll()
	{
		print(root);
	}
	
	// This method does an in-order traversal
	// of the tree in order to print the value
	// of each node.
	private Node print (Node current)
	{
		if (current == null)
			return current;
		else
		{
			print (current.left);
			System.out.println(current.data);
			print (current.right);
			return current;
		}
	}
	
	@SuppressWarnings(&quot;unchecked&quot;)
	public void remove(Comparable data)
	{
		root = remove (root, data);
	}
	
	@SuppressWarnings(&quot;unchecked&quot;)
	private Node remove (Node current, Comparable data) 
	{
		if (data.compareTo(current.data) == 0)
		{
			// Node has a right subtree, but no left subtree.
			if (current.left == null &amp;&amp; current.right != null)
			{
				Comparable childData = (Comparable) current.right.data;
				current.data = childData;
				current.right = null;
			}
			// Node has a left subtree, but no right subtree. 
			else if (current.left != null &amp;&amp; current.right == null)
			{
				Comparable childData = (Comparable) current.left.data;
				current.data = childData;
				current.left = null; 
				
			}
			// Node is a leaf node. 
			else if (current.left == null &amp;&amp; current.right == null)
				current = null;
			// Node has both a left &amp; right subtree. 
			else
			{
				Node successor = findInorderSuccessor(current.right); 
				current.data = successor.data;
				current.right = successor.right;
			}
			count--;
			return current;
		}
		else
		{
			if (data.compareTo(current.data) &gt; 0)
			{
				current.right = remove (current.right, data);
				return current;
			}
			else 
			{
				current.left = remove (current.left, data);
				return current;
			}
		}
	}
	
	@SuppressWarnings(&quot;unchecked&quot;)
	private Node findInorderSuccessor(Node current)
	{
		while (current.left != null)
			current = current.left;
		return current; 
	}
}</pre>
<a href="http://www.refactormycode.com/codes/1979-first-bst" style="color:#fff" title="As seen on RefactorMyCode.com"><img alt="Small_logo" src="http://www.refactormycode.com/images/small_logo.gif" style="border:0" /></a>

Refactor :my => 'code'

Recent

Popular

Pastable version of first BST