Preliminaries

• A tree can be defined in several ways. One natural way to define a tree is recursively. A tree is a collection of nodes. The collection can be empty; otherwise, a tree consists of a distinguished node r, called the root, and zero or more nonempty (sub)trees T1, T2, …, Tk, each of whose roots are connected by a directed edge from r.

  The root of each subtree is said to be a child of r, and r is the parent of each subtree root.
• Each node may have an arbitrary number of children, possibly zero. Nodes with no children are known as leaves.
• Nodes with the same parent are siblings
• A path from node n1 to nk is defined as a sequence of nodes n1, n2, …, nk such that ni is the parent of ni+1 for 1 ≤ i < k.
• The length of this path is the number of edges on the path, namely k − 1.
• There is a path of length zero from every node to itself.
• Notice that in a tree there is exactly one path from the root to each node.
• For any node ni, the depth of ni is the length of the unique path from the root to ni.
• The root is at depth 0.
• The height of ni is the length of the longest path from ni to a leaf.
• All leaves are at height 0.
• The height of a tree is equal to the height of the root.
• In each node, we have the data, a link to the first child and a link to the next sibling