A hierarchical ordering on a finite collection of objects may be described
as follows: each object with exactly
one exception has a *parent* object. The one exception is
is an object which has no parent and this exception is called the
*root*.

All objects which have the same parent are said to be *siblings*
and those objects are the *children* of the parent. An object
with no children is said to be a *leaf*.

A binary relationship $ a \le b $ (read as *a precedes or equals b*)
between two objects is said to be a hierarchical ordering if there is
a single root object $ r $ and:

- For all $ a $, $ a \le a $ and $ r \le a $ and ,
- If both $ a \le b $ and $ b \le a $ it follows that $ a = b $,
- The relationship is transitive: if $ a \le b $ and $ b \le c $, this implies that $ a \le c $, and
- If $ a \le c $ and $ b \le c $, this implies that either $ a \le b $ or $ b \le a $.

Two objects $ a $ and $ b $
are said to be *comparable* if either
$ a \le b $ or
$ b \le a $; otherwise, they are said to be
non-comparable.

Figure 1 shows a hierarchical ordering of twenty-one objects. You may observe with the local definition, all nodes except the root $ a_{00} \le c $ have a parent. For example, the object $ a_{25} $ has $ a_{12} $ as its parent; however, with the mathematical definition, we may also say that $ a_{00} \le a_{25}$, $ a_{25} \le a_{34}$, $ a_{25} \le a_{35}$, and $ a_{25} \le a_{40}$.

There are certain objects which are not comparable: for example, it is neither true that $ a_{21} \le a_{35}$ nor that $ a_{35} \le a_{21}$; however, there is exactly one sequence $ a_{00} \le a_{12} \le a_{25} \le a_{35}$; which begins at the root.

Figure 1. A hierarchical ordering on twenty-one objects.

Note that any linear ordering defines a trivial hierarchical ordering where objects have at most one child.

In general, most hierarchical orderings are explicitly defined by the programmer and the data structure is constructed through explicit definitions.

- Access the root object;
- Provide a means for traversing through the objects in a regular manner
(
*e*.*g*., depth- or breadth-first traversals); - Given a reference to an object in the hierarchical ordering:
- Access the parent of the object,
- Access the number of children,
- Determining if the object is a leaf (no children),
- Provide a means of stepping through the children, and
- Provide a means of traversing through all the descendants of the object, and
- Remove a means of removing the object and all its descendants;

- Given two objects, find the deepest common ancestor.

- Given a reference to an object, insert a child.