Tree ADTs

From

A tree is a finite set of elements called nodes. The set is either empty, or consists of a node called the root together with any number of successors which are also trees (subtrees in this case), which are disjoint from each other and from the root. The roots of the subtrees are called children of the root, and there is an edge from each node to its children, and a node is said to be the parent of its children. A node that has at least one child is called an internal node, and a node that has no children is called a leaf node.

More formally, in computer science, a tree is an acyclic connected graph where each node has a set of zero or more children nodes, and at most one parent node.

Paths

If n₁, n₂, …, n_n is a sequence of nodes in the tree such that ni is the parent of n_i+1, then this sequence is called a path. The length of the path is the number of edges, which is one less than the number of node: in this case the length of the path is n-1. If there is a path from a node M to a node N, then N is called a descendent of M and M is called an ancestor of N.

Depth/Level

The depth of a node M in the tree is the length of the path from the root to M. Thus the depth of the root is 0. The height of the tree is 1 more than the depth of the deepest node. All nodes at depth d are said to be at level d.