Tree vs Graph data structure
Before knowing about the tree and graph data structure, we should know the linear and non-linear data structures. Linear data structure is a structure in which all the elements are stored sequentially and have only single level. In contrast, a non-linear data structure is a structure that follows a hierarchy, i.e., elements are arranged in multiple levels.
Let’s understand the structure that forms the hierarchy.
In the above figure, we can assume the company hierarchy where A represents the CEO of the company, B, C and D represent the managers of the company, E and F represent the team leaders, and G and H represent the team members. This type of structure has more than one level, so it is known as a non-linear data structure.
What is Tree?
A tree is a non-linear data structure that represents the hierarchy. A tree is a collection of nodes that are linked together to form a hierarchy.
Let’s look at some terminologies used in a tree data structure.
- Root node: The topmost node in a tree data structure is known as a root node. A root node is a node that does not have any parent.
- Parent of a node: The immediate predecessor of a node is known as a parent of a node. Here predecessor means the previous node of that particular node.
- Child of a node: The immediate successor of a node is known as a child of a node.
- Leaf node: The leaf node is a node that does not have any child node. It is also known as an external node.
- Non-leaf node: The non-leaf node is a node that has atleast one child node. It is also known as an internal node.
- Path: It is a sequence of the consecutive edges from a source node to the destination node. Here edge is a link between two nodes.
- Ancestor: The predecessor nodes that occur in the path from the root to that node is known as an ancestor.
- Descendant: The successor nodes that exist in the path from that node to the leaf node.
- Sibling: All the children that have the same parent node are known as siblings.
- Degree: The number of children of a particular node is known as a degree.
- Depth of node: The length of the path from the root to that node is known as a depth of a node.
- Height of a node: The number of edges that occur in the longest path from that node to the leaf node is known as the height of a node.
- Level of node: The number of edges that exist from the root node to the given node is known as a level of a node.
Note: If there are n number of nodes in the tree, then there would be (n-1) number of edges.
How is a tree represented in the memory?
Each node will contain three parts, data part, address of the left subtree, and address of the right subtree. If any node does not have the child, then both link parts will have NULL values.
What is a Graph?
A graph is like a tree data structure is a collection of objects or entities known as nodes that are connected to each other through a set of edges. A tree follows some rule that determines the relationship between the nodes, whereas graph does not follow any rule that defines the relationship among the nodes. A graph contains a set of edges and nodes, and edges can connect the nodes in any possible way.
Mathematically, it can be defined as an ordered pair of a set of vertices, and a set of nodes where vertices are represented by ‘V’ and edges are represented by ‘E’.
G= (V , E)
Here we are referring to an ordered pair because the first object must be the set of vertices, and the second object must be a set of edges.
In Graph, each node has a different name or index to uniquely identify each node in the graph. The graph shown below has eight vertices named as v1, v2, v3, v4, v5, v6, v7, and v8. There is no first node, a second node, a third node and so on. There is no ordering of the nodes. Now, we will see how can we represent the edges in a graph?. An edge can be represented by the two endpoints in the graph. We can write the name of the two endpoints as a pair, that represents the edge in a graph.
There are two types of edges:
- Directed edge: The directed edge represents one endpoint as an origin and another point as a destination. The directed edge is one-way. For example, there are two vertices U and V; then directed edge would represent the link or path from U to V, but no path exists from V to U. If we want to create a path from V to U, then we need to have one more directed edge from V to U.
The directed edge can be represented as an ordered pair in which the first element is the origin, whereas the second element is the destination. - Undirected edge: The undirected edge is two-way means that there is no origin and destination. For example, there are two vertices U and V, then undirected would represent two paths, i.e., from U to V as well as from V to U. An undirected edge can be represented as an unordered pair because the edge is bi-directional.
The tree data structure contains only directed edges, whereas the graph can have both types of edges, i.e., directed as well as undirected. But, we consider the graph in which all the edges are either directed edges or undirected edges.
There are two types of graphs:
Directed graph: The graph with the directed edges known as a directed graph.
Undirected graph: The graph with the undirected edges known as a undirected graph. The directed graph is a graph in which all the edges are uni-directional, whereas the undirected graph is a graph in which all the edges are bi-directional.
Differences between tree and graph data structure.
| Basis for comparison | Tree | Graph |
|---|---|---|
| Definition | Tree is a non-linear data structure in which elements are arranged in multiple levels. | A Graph is also a non-linear data structure. |
| Structure | It is a collection of edges and nodes. For example, node is represented by N and edge is represented as E, so it can be written as: T = {N,E} | It is a collection of vertices and edges. For example, vertices are represented by V, and edge is represented as ‘E’, so it can be written as: T = {V, E} |
| Root node | In tree data structure, there is a unique node known as a parent node. It represents the topmost node in the tree data structure. | In graph data structure, there is no unique node. |
| Loop formation | It does not create any loop or cycle. | In graph, loop or cycle can be formed. |
| Model type | It is a hierarchical model because nodes are arranged in multiple level, and that creates a hierarchy. For example, any organization will have a hierarchical model. | It is a network model. For example, facebook is a social network that uses the graph data structure. |
| Edges | If there are n nodes then there would be n-1 number of edges. | The number of edges depends on the graph. |
| Type of edge | Tree data structure will always have directed edges. | In graph data structure, all the edges can either be directed edges, undirected edges, or both. |
| Applications | It is used for inserting, deleting or searching any element in tree. | It is mainly used for finding the shortest path in the network. |