Last Updated on February 2, 2023 by Prepbytes
We must first understand linear and non-linear data structures before learning about tree and graph in data structures. The linear data structure is a structure with just one level and sequential storage of all the components. A non-linear data structure, on the other hand, is one where the components are placed in numerous layers and follow a hierarchy.
Let’s examine the hierarchy’s organizational structure and see the difference between the tree and graph in data structure.
We can assume the firm hierarchy in the above diagram, where A stands in for the CEO, B, C, and D for the managers, E and F for the team captains, and G and H for the team members. This kind of organization, which includes several levels, is referred to as a non-linear data structure.
What is a Tree in Data Structure?
A non-linear data structure that describes the hierarchy is a tree. A tree is made up of a hierarchy-forming collection of nodes called nodes.
Let’s examine some of the terms used in tree data structures.
- Root node: A root node is the topmost node in a tree data structure. A node without any parents is referred to as a root node.
- Parent of a node: A node’s parent is the node that was immediately before it. Here, "predecessor" refers to the node that came before that specific node.
- Child of a node: A node’s immediate successor is referred to as a node’s child.
- Leaf node: A node that has no children is known as a leaf node. An external node is another name for it.
- Non-leaf node: A node that has at least one child node is referred to as a non-leaf node. An internal node is another name for it.
- Path: It consists of a string of parallel edges leading from a source node to a destination node. An edge in this case connects two nodes.
- Ancestor: An ancestor is one of the previous nodes that appear along the route from the root to that node.
- Descendant: The next nodes that line the route leading from that node to the leaf node.
- Sibling: Siblings are all the offspring with the same parent node.
- Degree: A degree is the number of a certain node’s children.
- Depth of node: The depth of a node is the distance along the route from the root to that node.
- Height of a node: The height of a node is the total number of edges along the longest route from that node to the leaf node.
- Level of node: A node’s level is defined as the number of edges connecting it to the given node from the root node.
Note: The number of edges in the tree would be (n-1) if there were n nodes.
How is a Tree Represented in the Memory?
The data portion, the left subtree address, and the right subtree address are the three components that make up each node. Both link portions will have NULL values if any node does not contain the child.
What is a Graph in Data Structure?
A graph is a collection of items or entities known as nodes that are connected to one another by a set of edges. It is similar to a tree data structure. A graph does not follow any rules that describe the relationship among the nodes, but a tree follows some rules that specify the relationship between the nodes. A graph is made up of nodes and edges, and the edges can link the nodes in any possible manner.
It may be described mathematically as an ordered pair of a set of vertices and a set of nodes, where vertices are denoted by the letter "V" and edges are denoted by the letter "E."
G= (V, E)Because the first item must be a collection of vertices and the second object must be a set of edges, we are speaking of an ordered pair in this context.
To uniquely identify each node in a network, each node has a unique name or index. Eight vertices in the network below are identified as v1, v2, v3, v4, v5, v6, v7, and v8. There are no first, second, third, and so on nodes. The nodes are not in any particular sequence. We will now look at how the edges of a graph can be represented. The graph’s two ends may be thought of as a representation of an edge.
Types of Edges in Graph:
-
Directed edge: One endpoint serves as the origin and another as the destination for the directed edge. A one-way directed edge exists. In the case of two vertices, U and V, the directed edge would indicate the connection or path between U and V, but there is no path connecting V and U. We require one additional directed edge from V to U in order to establish a route between V and U.
The origin of the directed edge is represented as the first element of an ordered pair, while the destination is represented by the second element. -
Undirected edge: Because the undirected edge is two-way, it lacks an origin and a destination. For instance, undirected would represent two pathways, namely those from U to V and from V to U, if there were two vertices, U and V. Because the edge is bi-directional, it may be represented as an unordered pair.
While the graph might include both directed and undirected edges, the tree data structure only stores directed edges. However, we take into account the graph whose edges are all either directed or undirected.
Types of Graphs:
Directed Graph: A directed graph is one that has directed edges.
Undirected Graph: Undirected graphs are those that have edges that are not directed. When a graph is undirected, all of its edges are bi-directional; when a graph is directed, all of its edges are uni-directional.
Differences Between Tree and Graph in Data Structure.
| The basis for comparison | Tree | Graph |
|---|---|---|
| Definition | A non-linear data structure called a tree has components grouped at different levels. | Another non-linear data structure is a graph. |
| Structure | It consists of a set of edges and nodes. For instance, it may be stated as T = {N, E} where N stands for the node and E for the edge. | It consists of a set of edges and vertices. For instance, it may be expressed as T = {V, E} where V stands for the vertex and E for the edge. |
| Root node | A parent node is a special type of node found only in the tree data structure. In the tree data structure, it stands for the topmost node. | A node in the graph data structure is singular. |
| Loop formation | No loops or cycles are produced by it. | A graph can have a loop or cycle. |
| Model type | Because nodes are grouped on different levels, a hierarchy is created, and as a result, the model is hierarchical. Any organization, for instance, will use a hierarchical organizational structure. | It is a model of a network. One social network that makes use of the graph data structure is Facebook. |
| Edges | An n-1 number of edges would exist if there were n nodes. | The graph determines how many edges there are. |
| Type of edge | Directed edges will always be present in tree data structures. | All edges in the graph data structure can either be directed, undirected or both. |
| Applications | It may be used to search for, insert, or remove any element inside a tree. | It is mostly used to determine the network’s shortest path. |
Conclusion:
We have quickly covered the concepts of the tree and graph in data structure in this post. We also concentrated on the main distinctions between them. These two ideas play a tremendously significant role in mathematics as well as being critical for computer science.