Tree vs Graph: Notable Difference You need to Know

By | April 26, 2020
Graph vs Tree

Tree and Graphs both belong to the Non-Linear Non-Primitive Data Structure. Both use nodes to represent many structures that are used to solve real-world problems. The tree uses a hierarchical model to represent its structure whereas a graph uses a network model to represent its structure.

There are many applications of tree and graph Data structure in the programming world and here in this article, we have compared these two data structures so you can find the difference between tree vs graph.

Vamware

Difference between Tree vs Graph

Before comparing both the structures tree vs graph, let’s have a look at are Non-Linear data structure and its type.

1. Non-Linear Data Structure

In a Non-Linear data structure, elements do not store in a sequential manner. Though there would be a relation between two elements and each element points to another element but they are not sequentially organized.

Types of Non-Linear Data Structure

There are two types of Non-Linear Data Structure:

  • Tree
  • Graph

1. Tree

A Tree is a hierarchical model Data Structure and it is a collection of the finite number of data elements and here data elements are nodes.

In tree data structure the main node is the root node, the topmost node of the structure and all the other nodes are its children and grandchildren nodes.

There are many types of Tree data structures and how the element stored in the tree depends upon the specific type of tree data structure.

Tree properties
  • Root Node: The Topmost node of the tree structure is known as the root node.
  • Edge: Edges are used to connect two nodes.
  • Parent Node: The nodes except including the Root Node in the structure having one or more than one reference node or pointing to other nodes are the parent nodes.
  • Child Node: The nodes which are connected by parent nodes are the Child code. In tree except for Root node, a parent node can be a child node.
  • Leaf Node: The node which does not have any child node in the structure is known as a leaf node. A leaf node could only be a child node and they lay at the bottom of the structure.
  • Subtree: Subtree can be classified as a part of a tree if we take the Root Node in the reference so from a root node there could be two subtrees derived.
  • Level: A level of a tree can be classified as the height of a tree. In Tree, the height ascends from Top to bottom, where Root node lay at 0 Level and the leaf node lay at the bottom level of a tree or subtree.

2. Graph

A graph is also a Non-Linear data structure, it is a collection of two sets vertices and edges, where vertices are the nodes and edges are the set of elements that connect two vertices. A Graph follows a Network model to represent its structure and the network model can form a closed loop. There are many types of Graphs and how the vertices are connected with edges depend upon the specific type of graphs

Properties of a Graph
  • Edges: Edge represents as E(v,w), where v and w are two vertices connected by edge E.
  • Vertices: Vertices are the nodes present the graph, connected with the help of edges.
  • Cycle: A graph structure where the first and the last vertices are the same

Tree vs Graph: Head to Head Comparison

Here we have described head to head comparison between Tree vs Graph in tabular form.

Graph

Tree

Path

A graph can have a bidirectional path between two vertices A tree can have only one path between two nodes

Root Node

There is a no concept of the root node in Graph Data Structure The root is the topmost node of the Tree data structure which does not have any parent node.

Tree Graph Theory

All graph cannot be a Tree All Tree can be a graph

Loop Structure

A Graph can have a loop structure, which means the last element and the first element are the same. A tree cannot have a loop structure.

Complexity

Graphs are more complex than Trees because they consist of the loop structure The tree is less complex as compared to Graphs

Traversal Tools

In Graph, we use BFS (Breadth-First Search) and DFS (Depth First Search) algorithms to traverse through each element. In Tree, we can use pre-order, in-order, and post-order algorithms to traverse through all elements.

Edge vs Vertices ratio

In Graph, there is no predefined edge vs vertices ratio. In a tree, if the structure has n number of vertices then it will have an n-1 number of edges.

Model Structure

A Graph Uses Network like model structure The tree uses hierarchical Like the model structure

Application

There are many applications of Graph structure such as:

  • Coloring of maps
  • Job scheduling
  • Algorithms of data science and machine learning
  • Sorting
  • Searching
  • Traversing
  • Binary search
  • Salesman problem

Types

  • Directed graph
  • Undirected graphs
  • Binary Tree
  • Binary Search Tree
  • AVL Tree
  • Heaps

 

Summary:

Tree Data structure follow a proper structure whereas there is no specific structure to a Graph. Every Tree is can be treated as a Graph whereas every graph can not be treated as Tree. Graph Data structure is mostly used to solve the real-world problem such as Salesman problem, and even Google maps use Graph and its searching algorithms to show the best path to its user whereas Tree data structure is mostly used in arranging data. There is a subtle difference between a tree and a graph, and in interviews, the difference between these two often asked.

You might be also interested in:

Leave a Reply

Your email address will not be published. Required fields are marked *