Trees in Data Structures

The tree is a data structure that allows you to associate a parent-child relationship between various pieces of data and thus allows us to arrange our records, files, and data in a hierarchical fashion. The tree is a very popular data structure used in a wide range of applications. 
A tree data structure can be defined as follows…
The tree is a non-linear data structure that organizes data in a hierarchical structure and this is a recursive definition.
A tree data structure can also be defined as follows…
The tree data structure is a collection of data (Node) that is organized in hierarchical structure, and this is a recursive definition.

In a tree data structure, we use the following terminology :

1) ROOT: In a tree data structure, the first Node is called Root Node. Every tree must have a root node. We can say that the root node is the origin of the tree data structure. In any tree, there must be only one root node. We never have multiple root nodes in a tree.

2) EDGE: In a tree data structure, the connecting link between any two nodes is called EDGE. There will be a maximum of ‘N-1′ number of edges in a tree with an’ N’ number of nodes.

3) PARENT: In a tree data structure, the Node, which is a predecessor of any node, is called as PARENT NODE. In simple words, the Node with a branch from it to any other node is called a parent node. A parent node can also be defined as “The Node which has child / children”.

4) CHILD: In a tree data structure, the Node, a descendant of any node, is called a CHILD Node. In simple words, the Node with a link from its parent node is called a child node. In a tree, any parent node can have any number of child nodes. Thus, in a tree, all the nodes except the root are child nodes.

5) SIBLINGS: In a tree data structure, nodes that belong to the same Parent are called SIBLINGS. In simple words, the nodes with the same Parent are called Sibling nodes.

6) LEAF: In a tree data structure, the Node which does not have a child is called LEAF Node. In simple words, a leaf is a node with no child. In a tree data structure, the leaf nodes are also called External Nodes. External Node is also a node with no child. In a tree, a leaf node is also called a Terminal Node.

7) INTERNAL NODES: In a tree data structure, the Node which has at least one child is called as INTERNAL NODE. In simple words, an internal node is a node with at least one child. In a tree data structure, nodes other than leaf nodes are called Internal Nodes. The root node is also an Internal Node if the tree has more than one Node. Internal nodes are also called ‘Non-Terminal’ nodes.

8) DEGREE: In a tree data structure, the total number of children of a node is called DEGREE of that Node. In simple words, the degree of a node is the total number of children it has. Therefore, the highest degree of a node among all the nodes in a tree is called the ‘Degree of Tree.’

9) LEVEL: In a tree data structure, the root node is said to be at Level 0, and the children of the root node are at Level 1, and the children of the nodes which are at Level 1 will be at Level2 and so on… In simple words, in a tree, each step from top to bottom is called as a Level and the Level count start with ‘0’ and are incremented by one at each level (Step).

10) HEIGHT: In a tree data structure, the total number of edges from the leaf node to a particular node in the longest path is called as HEIGHT of that Node. In a tree, the height of the root node is said to be the height of the tree. In a tree, the height of all leaf nodes is ‘0’.

11) DEPTH: In a tree data structure, the total number of edges from a root node to a particular node is called as DEPTH of that Node. In a tree, the total number of edges from a root node to a leaf node in the longest path is said to be the depth of the tree. In simple words, the highest depth of any leaf node in a tree is said to be the depth of that tree. Thus, in a tree, the depth of the root node is ‘0.

12) PATH: In a tree data structure, the sequence of Nodes and Edges from one Node to another node is called PATH between that two Nodes. The length of a Path is the total number of nodes in that path. 

Maroju Sanjana



Categories: News