Tree vs Graph

By | August 23, 2019

Tree and Graphs both belong to the Non-Linear Non-Primitive Data Structure. Both use nodes to represent many structures which are used to solve the 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 programming world and here in this article, we have compared these two data structures so you can find the difference between them.

Tree vs Graph

Before comparing both the structures lets have a look at what are Non-Linear data structure and its type.

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

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 depend 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.

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 which 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

Graph vs Tree: Head to Head Comparison

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 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 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

People Also Read:

Leave a Reply

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