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?

This site uses Akismet to reduce spam. Learn how your comment data is processed.