A rooted tree is a tree with a node named as root of the tree. A tree which does not has root node, is sometimes called a free tree/unrooted tree (A tree which does not have a root node). Although the term “tree” generally refers to a free tree.
Fig. 1: Rooted trees
Terminologies used:
- Root: Node at the top of the tree.
- Parent: Any node, except root has exactly one edge running upward to another node. The node above it is called it’s parent.
Example: in fig. 1 (last row, 1st tree) parent of node B is node A, parent of node C is node B. - Child: Any node may have one or more lines running downward to other nodes. Nodes below are children.
Example: in fig. 1 (last row, 2nd tree) nodes B and C are children of node A and node D is children of node B. - Siblings: A group of nodes with the same parent.
- Leaf: A node that has no children.
Example: in fig. 1 (last row, 2nd tree) nodes D and C are leaf nodes. - Subtree: Any node can be considered to be the root of a subtree, which consists of its children and its children’s children and so on.
Fig. 2: Subtree
The numbers of rooted trees on n nodes for n=1, 2, … are 1, 1, 2, 4, 9, 20, 48, 115, 286….. (sequence A000081 in the OEIS).