Tree (ADT)

The Tree ADT stores elements at positions which are defined relative to neighbouring positions.

A tree also similarly provides a Position with the method element() which returns the object stored at the position.

Accessor methods:

• position root(): return the tree’s root; error occurs if tree is empty
• position parent(v): return the parent of $v$; error occurs if $v$ is root
• Iterable children(v): returns an iterable collection containing the children of node $v$

Query methods:

• boolean isInternal(v): test whether node $v$ is internal
• boolean isExternal(v): test whether node $v$ is external
• boolean isRoot(v): test whether node $v$ is a root

Generic methods:

• integer size(): return the number of nodes in the tree
• boolean isEmpty(): test whether the tree has any nodes
• Iterator iterator(): return an iterator of nodes stored in tree
• Iterable positions(): return iterable collection of all nodes in tree
• element replace(v, e): replace element stored at $v$ with $e$ and return it