Java/Binary Search Trees

Binary Search Tree Class

For more details about the binary search tree abstract data type, see Binary Search Trees/ADT.

For more details about all abstract data types, see Abstract Data Types.

The binary search tree type is a generally useful data container that can be implemented multiple ways. The real goal here is to keep the implementation of the binary tree abstract data type lightweight and uncomplicated.

Organization

The organization of the binary search tree abstract data type class is as follows:

• BinaryNode class to represent nodes in the binary tree (the binary tree class owns this class and manipulates these binary nodes directly).
• Constructor to create empty tree
• Insert method to add items to the binary tree
• Remove method to remove items from the binary tree
• Contains/Search method to find items in binary tree
• findMin/findMax methods to find minimum and maximum elements in trees/subtrees

These methods are all implemented with recursion.

Binary Node Class

Here is the binary node class - again, kept simple, with the focus being on the implementation/application and not on extra features:

	class BinaryNode { 
		Integer element;
		BinaryNode left, right;

		public BinaryNode(Integer e, BinaryNode l, BinaryNode r) { 
			this.left = l;
			this.right = r;
			this.element = e;
		}

		public String toString() { return this.element.toString(); }
		public Integer getElement() { return this.element; }
		public void setElement(Integer e) { this.element = e; }

		public BinaryNode getLeft() { return this.left; }
		public BinaryNode getRight() { return this.right; }

		public void setLeft(BinaryNode newChild) { this.left = newChild; }
		public void setRight(BinaryNode newChild) { this.left = newChild; }
	}

Driver

A driver utilizing the binary search tree would look something like this: