Binary Trees/OOP

Notes on object oriented principles when implementing binary trees.

Delegating responsibility for tasks:

for example how do you decide if the left/right method should be node.left, node.getLeft(), or tree.left(node)?
when designing a data structure, think ahead to the concrete implementation and how this will be extended.
trees have a complicated potential inheritance diagram...
- Different concrete implementations - linked vs array
- Different functionality (expressions vs search)
- Further, internal classes and utilities might change (AVL trees)
- Trees are used by other data structures (maps, sets, sorting, etc.)
Nail down the scope before you start
Not sure why, but it seems better to build it into the TREE whenever possible
However, if you can access data directly, like node.left = new Node(), why not do it that way?

Positions vs. Nodes

The Goodrich book makes a big deal about separating tree positions vs. tree nodes
This over-complicates things, but it boils down to this: the user is going to need positions in a tree for various algorithms, so the Position class gives them an object that they can use to point at particular nodes.
This avoids the cost of looking an item up if it is used over and over again - you just pass the position in, and get the node. (But what's the cost of looking up the node?)
The tree then has a validate() method, which turns Position objects into Node objects, so that it can manipulate the tree itself.
The book doesn't explicitly cover this kind of extra-layer-of-protection object model, but it is worth nothing.

Reusability and adaptability:

Hook methods, particular application in this case was the Euler tour and the previsit/postvisit action hooks
Hook methods give you a pseudo-virtual method - can be extended, not just from class to class, but from action to action

Generic types

Generic types for node data, extends to tree structure
Decide whether you want an elements-and-values based structure <E> or a key-value based structure <K,V> early