Tree vs Graph: Data Structure
Difference Between Tree and Graph
What is Tree?
A tree is a non-linear data structure and finite collection of elements called node. A tree, in which the data items are arranged in hierarchical order basically a tree, shows the hierarchy among the data items. It organizes the data items into branches and a tree does not contain any cycle.
If we talk about the types of tree, so there are many types of tree like; Binary tree, Binary search tree, AVL tree, Red-black tree, B-tree, B+ tree, Splay tree etc. According to the requirement of the application, we can use appropriate tree.
Now we are discussing the properties of the tree:
- A tree contains root node which is designated as top node of the tree.
- A tree is divided into sub-trees which contain remaining elements of the tree.
- A tree is expanded itself top to bottom.
- A tree always contains a path which means the root node must be connected to all others node of the tree.
- A tree doesn’t contain any cycle or loop.
- A tree contains n-1 edges in it.
What is Graph?
A graph is also a non-linear data structure. It contains a group of nodes called vertices of the graph and set of lines called edges of the graph which are used to connect the two nodes or vertices. In graph, we represent the vertices or nodes by the circle or point and for the edges, we use the arc or line segments. An edge is mathematically represented by E(v,w) where the v and w are pairs of the nodes or vertices. The graph can contain cycle or loops.
There are many categories of graph like; directed graph, un-directed graph, connected graph, non-connected graph, simple graph and multi graph etc. The graph is used in computer network, electrical circuits, social networking etc.
Now we are discussing the properties of the graph:
- In graph, a vertex or node can be connected to more than one vertex using edges.
- In graph, an edge could be directed or bi-directed.
- In graph, we can provide the weighted on the edges of the graph
- A graph can contain loops.
Difference Between Tree and Graph
| parameters | TREE | GRAPH |
| Path | In tree, there is only one path between two vertices | In graph, more than one path is allowed between two vertices |
| Root node | A tree contains one root called top of the tree. | Graph doesn't have a root node. |
| Loops | In tree, there is no cycle or loops allowed | The graph can contain cycle or loops |
| Implementation | A tree is easy to implement as compared to graph. | The graph is more difficult to implement as compared to tree. |
| Complexity | A tree takes less time to perform operations | The graph takes more time to perform operations as compared to tree. |
| Traversal techniques | A tree can be traversed by Pre-order, In-order, Post-order traversals | A tree can be traversed by Breadth-first search and depth-first search. |
| Number of edges | A tree has n-1edges (where n is the number of nodes) | Not defined |
| Model type | A tree follows Hierarchical model | The graph follows network model. |