Difference Between Tree and Graph

Tree and graph come under the category of non-linear data structure where tree offers a very useful way of representing a relationship between the nodes in a hierarchical structure and graph follows a network model. Tree and graph are differentiated by the fact that a tree structure must be connected and can never have loops while in the graph there are no such restrictions.

A non-linear data structure consists of a collection of the elements that are distributed on a plane which means there is no such sequence between the elements as it exists in a linear data structure.

Content: Tree Vs Graph

1. 1. Comparison Chart
   2. Definition
   3. Key Differences
   4. Conclusion

Comparison Chart

Basis for comparison	Tree	Graph
Path	Only one between two vertices.	More than one path is allowed.
Root node	It has exactly one root node.	Graph doesn't have a root node.
Loops	No loops are permitted.	Graph can have loops.
Complexity	Less complex	More complex comparatively
Traversal techniques	Pre-order, In-order and Post-order.	Breadth-first search and depth-first search.
Number of edges	n-1 (where n is the number of nodes)	Not defined
Model type	Hierarchical	Network

Definition of Tree

A tree is a finite collection of data items usually termed as nodes. As it is mentioned above that a tree is a non-linear data structure which arranges data items in sorted order. It is used to show a hierarchical structure between the various data elements and organizes the data into branches which relate the information. The addition of a new edge in a tree results in a formation of the loop or circuit.

There are several types of trees such as a binary tree, binary search tree, AVL tree, threaded binary tree, B-tree, etc. Data compression, file storage, manipulation of the arithmetic expression and game trees are some of the application of tree data structure.

Properties of tree:

• There is designated node at the top of the tree known as a root of the tree.
• The remaining data items are divided into disjoint subsets refer to as subtree.
• The tree is expanded in height towards the bottom.
• A tree must be connected which means there must be a path from one root to all other nodes.
• It does not contain any loops.
• A tree has n-1 edges.

There are various terms associated with trees such as terminal node, edge, level, degree, depth, forest, etc. Among those terms, some of them described below.

• Edge – A line which connects two nodes.
• Level – A tree is partitioned into levels such a way that the root node is at level 0. Then, its immediate children are at level 1, and its immediate children are at level 2 and so on up to the terminal or leaf node.
• Degree – It is the number of subtrees of a node in a given tree.
• Depth – It is the maximum level of any node in a given tree and also known as height.
• Terminal node – The highest level node is terminal node while other nodes except terminal and root node are known as non-terminal nodes.

Definition of Graph

A graph is also a mathematical non-linear data structure which can represent various kinds of physical structure. It consists of a group of vertices (or nodes) and set of edges that connect the two vertices. Vertices on the graph is represented as point or circles and edges are shown as arcs or line segments. An edge is represented by E(v,w) where v and w are the pairs of vertices. Removal of an edge from a circuit or connected graph creates a subgraph that is a tree.

The graphs are classified into various categories such as directed, non-directed, connected, non-connected, simple and multi-graph. Computer network, transportation system, social network graph, electrical circuits and project planning are some of the applications of graph data structure. It is also employed in management technique named as PERT (program evaluation and review technique) and CPM (critical path method) in which the graph structure is analysed.

Properties of a graph:

• A vertex in a graph can be connected to any number of other vertices using edges.
• An edge can be bidirected or directed.
• An edge can be weighted.

In graph also we use various terms like adjacent vertices, path, cycle, degree, connected graph, complete graph, weighted graph, etc. Let’s understand some of these terms.

• Adjacent vertices – A vertex a is adjacent to vertex b if there is an edge (a,b) or (b,a).
• Path – A path from a random vertex w is an adjacent sequence of vertices.
• Cycle – It is a path where the first and last vertices are the same.
• Degree – It is a number of edges incident on a vertex.
• Connected graph – If there exists a path from a random vertex to any other vertex, then that graph is known as a connected graph.

Conclusion

Graph and tree are the non-linear data structure which is used to solve various complex problems. A graph is a group of vertices and edges where an edge connects a pair of vertices whereas a tree is considered as a minimally connected graph which must be connected and free from loops.