Binary Search Trees/ADT

See Trees/ADT or Binary Trees/ADT

Trees

Binary trees should follow the basic tree ADT and implement:

• size
• isempty

Further:

• iterable
• depth
• height

Utility methods (confusing, b/c using Tree, but checking Node...)

• isInternal
• isExternal
• isLeaf
• isRoot
• parent
• children
• numberOfChildren

Trees:

• allPositions
• iterator

Some of these can be left out, particularly in a trimmed-down binary tree.

Binary Trees

The binary tree implementation can replace the children functionality with a left and right. See Binary_Trees/ADT, which we follow here.

Node class provides two methods to access two children:

• left/getLeft
• right/getRight

Additional:

• sibling
• parent

Support iteration:

• positions() should return all positions in tree
• iter() should make it iterable

Trimming Down

To really trim things down, our binary search tree only implements a few methods, so we can focus on the actual search tree organization.

The minimal methods for a binary search tree are:

• insert
• remove
• contains/find

Optionally:

• findMin/findMax

These are "easiest" to implement recursively (and usually, easiest to handle the empty case separately.)