What does the Tree ADT provide, and what role does a Position play in it?

A Position is the abstraction of a node: it gives access to the stored element via getElement() without exposing how the node is implemented. The Tree ADT offers access methods (root, parent, children, numChildren), query methods (isInternal, isExternal, isRoot) and helpers (size, isEmpty, iterator).

Positions. Code that uses a tree needs a way to point at "this node" without depending on whether nodes are linked objects or array slots. A Position is that handle. You can ask it for its element, and you pass it back to the tree to ask about its neighbours.

Access methods:

• root() — the position of the root
• parent(p) — the parent of p
• children(p) — the children of p, as an iterable list of positions
• numChildren(p) — how many children p has

Query methods: isInternal(p), isExternal(p), isRoot(p).

Helper methods: size(), isEmpty(), and iterator() over the elements.

With these, all the standard algorithms (depth, height, the traversals) can be written once and run on any tree implementation.