Binary trees are an efficient way of storing arbitrary amounts of data that has to be searched frequently or kept in sorted order even though there are many changes being made. Today we will discuss binary trees in general and look at pseudocode for implementing a binary search tree data structure. In this case, we will make the class more useful by utilizing Java generics from the very beginning so that we end up with a generalized binary tree class that handles any non-primitive data type. Primitive data types will be easily handled using this data structure by encapsulating each primitive data type in its respective wrapper class.
We will discuss how items are inserted into and removed from a binary search tree. We will also discuss how to search for an item in the tree and look at different ways of traversing a binary tree (preorder, inorder, postorder).
Pseudocode for a binary tree class is posted and will be updated if we make significant changes. We can use this in class as a starting point for writing our own binary tree implementation.