Tree Data Structure | Tree Terminology

Tree Data Structure-

 

Tree data structure may be defined as-

 

Tree is a non-linear data structure which organizes data in a hierarchical structure and this is a recursive definition.

OR

A tree is a connected graph without any circuits.

OR

If in a graph, there is one and only one path between every pair of vertices, then graph is called as a tree.

 

Example-

 

 

Properties-

 

The important properties of tree data structure are-

  • There is one and only one path between every pair of vertices in a tree.
  • A tree with n vertices has exactly (n-1) edges.
  • A graph is a tree if and only if it is minimally connected.
  • Any connected graph with n vertices and (n-1) edges is a tree.

 

To gain better understanding about Tree Data Structure,

Watch this Video Lecture

 

Tree Terminology-

 

The important terms related to tree data structure are-

 

 

1. Root-

 

  • The first node from where the tree originates is called as a root node.
  • In any tree, there must be only one root node.
  • We can never have multiple root nodes in a tree data structure.

 

Example-

 

 

Here, node A is the only root node.

 

2. Edge-

 

  • The connecting link between any two nodes is called as an edge.
  • In a tree with n number of nodes, there are exactly (n-1) number of edges.

 

Example-

 

 

3. Parent-

 

  • The node which has a branch from it to any other node is called as a parent node.
  • In other words, the node which has one or more children is called as a parent node.
  • In a tree, a parent node can have any number of child nodes.

 

Example-

 

 

Here,

  • Node A is the parent of nodes B and C
  • Node B is the parent of nodes D, E and F
  • Node C is the parent of nodes G and H
  • Node E is the parent of nodes I and J
  • Node G is the parent of node K

 

4. Child-

 

  • The node which is a descendant of some node is called as a child node.
  • All the nodes except root node are child nodes.

 

Example-

 

 

Here,

  • Nodes B and C are the children of node A
  • Nodes D, E and F are the children of node B
  • Nodes G and H are the children of node C
  • Nodes I and J are the children of node E
  • Node K is the child of node G

 

5. Siblings-

 

  • Nodes which belong to the same parent are called as siblings.
  • In other words, nodes with the same parent are sibling nodes.

 

Example-

 

 

Here,

  • Nodes B and C are siblings
  • Nodes D, E and F are siblings
  • Nodes G and H are siblings
  • Nodes I and J are siblings

 

6. Degree-

 

  • Degree of a node is the total number of children of that node.
  • Degree of a tree is the highest degree of a node among all the nodes in the tree.

 

Example-

 

 

Here,

  • Degree of node A = 2
  • Degree of node B = 3
  • Degree of node C = 2
  • Degree of node D = 0
  • Degree of node E = 2
  • Degree of node F = 0
  • Degree of node G = 1
  • Degree of node H = 0
  • Degree of node I = 0
  • Degree of node J = 0
  • Degree of node K = 0

 

7. Internal Node-

 

  • The node which has at least one child is called as an internal node.
  • Internal nodes are also called as non-terminal nodes.
  • Every non-leaf node is an internal node.

 

Example-

 

 

Here, nodes A, B, C, E and G are internal nodes.

 

8. Leaf Node-

 

  • The node which does not have any child is called as a leaf node.
  • Leaf nodes are also called as external nodes or terminal nodes.

 

Example-

 

 

Here, nodes D, I, J, F, K and H are leaf nodes.

 

9. Level-

 

  • In a tree, each step from top to bottom is called as level of a tree.
  • The level count starts with 0 and increments by 1 at each level or step.

 

Example-

 

 

10. Height-

 

  • Total number of edges that lies on the longest path from any leaf node to a particular node is called as height of that node.
  • Height of a tree is the height of root node.
  • Height of all leaf nodes = 0

 

Example-

 

 

Here,

  • Height of node A = 3
  • Height of node B = 2
  • Height of node C = 2
  • Height of node D = 0
  • Height of node E = 1
  • Height of node F = 0
  • Height of node G = 1
  • Height of node H = 0
  • Height of node I = 0
  • Height of node J = 0
  • Height of node K = 0

 

11. Depth-

 

  • Total number of edges from root node to a particular node is called as depth of that node.
  • Depth of a tree is the total number of edges from root node to a leaf node in the longest path.
  • Depth of the root node = 0
  • The terms “level” and “depth” are used interchangeably.

 

Example-

 

 

Here,

  • Depth of node A = 0
  • Depth of node B = 1
  • Depth of node C = 1
  • Depth of node D = 2
  • Depth of node E = 2
  • Depth of node F = 2
  • Depth of node G = 2
  • Depth of node H = 2
  • Depth of node I = 3
  • Depth of node J = 3
  • Depth of node K = 3

 

12. Subtree-

 

  • In a tree, each child from a node forms a subtree recursively.
  • Every child node forms a subtree on its parent node.

 

Example-

 

 

13. Forest-

 

A forest is a set of disjoint trees.

 

Example-

 

 

To gain better understanding about Tree Terminology,

Watch this Video Lecture

 

Download Handwritten Notes Here-

 

 

Next Article- Binary Tree | Types of Binary Trees

 

Get more notes and other study material of Data Structures.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
Tree Data Structure | Tree Terminology
Article Name
Tree Data Structure | Tree Terminology
Description
Tree data structure is a non-linear data structure. Tree Terminology in Data Structure- Level of a Tree, Height of a Tree, Depth of Tree, Degree of a Tree, Root of Tree, Internal Node, Leaf Node, Edge, Parent, Child, Siblings, Subtree, Forest. All these terms are discussed with examples.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-