Tree Terminology in Data Structure

A tree is a finite set of vertices connected by edges such that-
i. There is one specially designated vertex called root.
ii. The remaining vertices are partitioned into a collection of sub-trees T1, T2, T3,…, Tn each of which is a tree.

Basic Tree Terminology:

Root: A node without any parent is called a root node.

Node: Each data item in a tree is called a node.

Edge: The line drawn from one node to another node is called an edge.

Internal Node: A node with at least one child is called an internal node.

External Node: A node without any children is called an external node or leaf node.

Degree of a node: The number of sub-trees of a node is called its degree.

Degree of a tree: It is the maximum degree of nodes in a tree.

Siblings: The nodes who share the same parent are called siblings.

Ancestor and Descendant: A node n is an ancester of node m and m is descendant of n if n is either the father of m.

Level: Number of ancestors of nodes is called its level. Each node in a tree is assigned a level number as follows:
1. The root of the tree is at level 0.
2. Level of other node=level of its parent +1.

Depth: The depth of a tree T can be defined as follows:
depth of T = maximum level number of T+1

Path and Path length: It is a sequence of consecutive edges from the source node to the destination node. The number of edges in a path is called path length.

Branch: Path ending in a leaf node is called as Branch.

Internal Path length: Internal path length of a tree can be defined as the sum of the levels of all the internal nodes in the tree.

External Path length: External path length of a tree can be defined as the sum of the levels of all the external nodes in the tree.

Forest: A set of disjoint trees are called a forest.