Tree | Definitions

Prateek Chauhan
May 22, 2020
3 min read

Updated: Jun 29, 2020

A tree data structure can be defined as follows:-

A tree is a non-linear data structure that organizes data in a hierarchical structure and this is a recursive definition.

In a tree, every individual element is called a Node. It stores the actual data of that particular element and links it to the next element in a hierarchical structure.

If we have N number of nodes then we can have a maximum of N-1 number of links.

Terminologies used in Tree Data Structure:

1) Root:

In a tree data structure, the first node is called the Root Node. We can say that the root node is the origin of the tree. In any tree, there must be only one root node.

In below figure Node 'A' represents the root node

2) Edge:

In a tree data structure, the connecting link between any two nodes is called Edge. In a tree with 'N' number of nodes, there will be a maximum of 'N-1' number of edges.

3) Parent:

In simple words, the node which has 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".

In below figure 'A', 'B', 'C' , 'E', 'G' are parent nodes.

4) Child:

In simple words, the node which has a link from its parent node is called a child node. In a tree, any parent node can have any number of child nodes. In a tree, all the nodes except root are child nodes.

In the above figure :

'B' & 'C' are children of 'A'.
'G' & 'H' are children of 'C'.
'D', 'E' & 'F' are children of 'B'.
'I' & 'J' are children of 'E'.
'K' is a child of 'G'.

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.

In the above figure:

'B' & 'C' are siblings.
'D', 'E', 'F' are siblings.
'G', 'H' are siblings.
'I', 'J' are siblings.

6) Leaf:

In a tree data structure, the node which does not have a child is called a Leaf Node. In simple words, a leaf is a node with no child.

In a tree data structure, the leaf nodes are also called as External Nodes. The external node is also a node with no child. In a tree, a leaf node is also called 'Terminal' node.

In above figure 'D', 'F', 'I', 'J', 'K', 'H' are leaf nodes.

7) 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 said to be Internal Node if the tree has more than one node. Internal nodes are also called as 'Non-Terminal' nodes.

In above figure 'A', 'B', 'E', 'C', 'G' are internal nodes.

8) Degree:

In simple words, the Degree of a node is the total number of children it has. The highest degree of a node among all the nodes in a tree is called as 'Degree of Tree'.

In the above figure:

The degree of 'B' is 3.
The degree of 'A' is 2.
The degree of 'F' is 0.

9) Level:

In a tree, each step from top to bottom is called a Level and the Level count starts with '0' and incremented by one at each level (Step).

10) Height:

In a tree data structure, the total number of edges from a 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, the total number of edges from the 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. 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 a PATH between those two Nodes. The length of a Path is the total number of nodes in that path. In the below example the path A - B - E - J has length 4.