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.