- every entry is a node that has links to:
- a single parent node (unless it's root)
- a number of child nodes (if any)

- there is a single root node all others descend from directly or indirectly. This node is the only entry that has a nil parent.
- by following child nodes recursively, no node should be able to reach itself (it should be acyclic)
- there must be a single path from one node to another (no reference is duplicated)

One of the reasons why textbooks do not mention trees as abstract data type is that in usage they are *almost* irreducible to a common ground: each type of tree chosen reflects a very different need, requiring fundamentally different operations. Of all, only these two are universally common:

Operation |
Arguments |
Returns |
Description |

getSize | ULONG | Gets number of nodes in tree. | |

getRoot | NODE | Gets root node from tree. |

On this opaque definition, there are endless varieties built to address a particular need. Most commonly used are:

- Standard Tree: a tree in which node can have no matter how many children
- Strengths:
- good to store node hierarchies without any special rules
- memory/speed efficiency

- Weaknesses:
- ordering is very costly
- search is very slow, unless nodes are stored in a Hash Table as well

- Strengths:
- Binary Search Tree: a tree in which node can only have two children at most, able to rebalance itself
- Strengths:
- good when someone wants tree nodes to be self-sorted
- good for node searches

- Weaknesses:
- slow at any operation that may require rebalancing (inserts, deletes)
- higher memory consumption

- Strengths:

This time complexity table using Big O Notation shows advantages and disadvantages of each data structure chosen for each tree operation:

Operation |
Standard Tree | Binary Search Tree |

getSize | O(1) | O(1) |

getRoot | O(1) | O(log(N)) |

**Conclusion**: Standard Tree backed by a Hash Table, with its speed/memory efficiency advantages, should be solution of choice unless one specifically desires structure to be self-ordered!