Rooted Tree

Ankur Kulhari

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.

Rooted 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).

What do you think about the article?