let be a finite set. a rootedd tree on is defined by the pair where is a function such that
- there is no positive integer such that for some element , and
- there is exactly one element such that , called the root.
for each nonroot node , is called the parent of in the tree, and the ordered pair is called the parent arc of in the tree. an arc of the tree is the parent arc of some nonroot node. if the parent of is then is a child of and is the child arc of .
a rooted tree has arity if every node has at msot children. a binary tree is a tree that has arity 2.
we say two nodes are adjacent if one is the parent of the other. we say the arc is incident to the nodes and .
the ancestors of are defined inductively: is its own ancestor, and (if is not the root) the ancestor's of 's parent are also ancestors of . if is the ancestor of then is a descendant of . we say is a proper ancestor of (and is a proper descendant of ) if is an ancestor of and . the depth of a node is the number of proper ancestors it has.