Nodes in ‘Trees’ data-structure

The tree data structure is a set of nodes which are formed in a hierarchical structure that would seem something like a structure of a real tree.

We can see that there is a hierarchy going on from the top to the bottom, where every circle represents nodes, which hold data that in our case our alphabet letters — a, b, c, d, e, f, g, h and the arrows joining these nodes are called — Edges.

Some essential terminologies related to trees:

• The node which has a child from it to any other node is called — Parent Node.
• The node which is descendant of any node is called — Child Node

For example, if we choose node A as the parent node then node B and C are descendants of node A, so node B and node C are the child nodes of A. Likewise, if we take note B as the parent node then nodes D, E, F are its child nodes. In the above picture, all nodes except A are child nodes as all nodes except A have a parent node.

• The first(starting) node of the tree is called — Root Node

The node A that is in the above picture is the Root Node of the tree. As we can see the root node is the start (origin) of the tree data-structure and in any tree, there is only one Root Node.

• The node which does not have a child is called — Leaf Node

In our above example, we can see node D, F and G have no child, thus they are Leaf Nodes. The Leaf Nodes are sometimes also referred as - External Nodes.

• The node which has at least one child is called — Internal Node

Data in our example node A, B, C, E are internal nodes because they have at least one child.

• The total amount of children of a node is called — Degree of that Node

That is the Degree of Node A is 2, as it holds child B and C. The Degree of Node B is 3 as it has three child nodes, those are D, E and F. The Degree of Node C is 1, as it has only one child G and finally the Degree of Nodes D, F, G, and H are zero as they don’t hold any child nodes.

• The highest degree of a node among all the nodes is called — Degree of the Tree

In the above example, node B has the highest degree which is three. Thus the Degree of the Tree is also three.

• In a tree, each step from the highest to the lowest node is called — Level

We begin the levels from the root node taking it as Level zero. In our example node A is at Level 0, moving forward node B and C are at Level 1, node D, E, F and G are at Level 2 and node H is Level 3. Those were brief terminologies for tree nodes.