Java/Binary Search Trees

Binary Search Tree Class

For more details about the binary search tree abstract data type, see Binary Search Tree/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.