Graph And Tree
What do you understand by graphs and trees? You might have listened to these terms other than in coding, but it plays an essential role in the technical rounds of FAANG companies. So these two topics are a must-do for the interviews.
A graph is a non-linear data structure used to represent the networks, and it consists of vertices(V), or it can be called nodes and edges(E) that connect the pair of nodes.
- In the graph, the edge can be directed or bidirected.
- It can be weighted.
There are two commonly used representations of a graph are:
1. Adjacency Matrix
2. Adjacency List
The other vital non-linear data structure is trees that offer relationships between the nodes in a structure and consist of nodes and edges, which arranges data items in sorted order and cannot be in the form of a cycle and should always be connected unlike graphs.
There are several types of trees, such as a binary tree, binary search tree, AVL tree, threaded binary tree, B-tree, etc.
- The topmost node is the tree's root, and all other nodes connected to it are its children(sub-nodes).
- It does not contain any loop.
Difference between graph and tree
|A graph consist of vertices/nodes and edges.|
Tree consists of nodes and the edges.
A graph can have loops and self-loops.
A tree cannot have loops and self- loops.
A graph can have connected and disconnected components.
A tree should always be connected.
|A graph can be traversed using Depth- First Search(DFS) and Breadth-First Search(BFS).|
A tree can be traversed using inorder, preorder, and postorder techniques.
|A graph is more complex compared to trees due to loops.|
It is less complex in comparison to graphs.
|It doesn’t have any root node.|
The topmost node is the root node of the tree.
|It is a network model.|
It is a hierarchical structure.
|It can have unidirectional and bidirectional paths between the nodes.|
There is only one path between two nodes.
No predefined number of edges.
There are n-1 edges, where n is the number of vertices.
1). What is the key difference between graph and tree?
A graph can have loops or self-loops, whereas trees cannot have any loops.
A graph can have connected or disconnected components, whereas nodes in the tree should be connected.
2). What are the methods to traverse a graph?
There are two methods to traverse a graph: Depth First Search(DFS) and Breadth-First Search(BFS).
3). Difference between DFS and BFS?
DFS uses Stack data structure, and BFS uses Queue data structure.
The Time complexity of BFS is O(V + E) when Adjacency List is used and O(V^2) when Adjacency Matrix is used.
The Time complexity of DFS is also O(V + E) when Adjacency List is used and O(V^2) when Adjacency Matrix is used.
In this blog, we have covered the two non-linear data structures and how they differ in their properties.
Graphs and trees are used to solve various complex problems in competitive programming. The graph is a data structure where vertices are connected using edges and form a cycle. Whereas Trees is a data structure where the topmost node is the tree's root, and all others are its children, it cannot have a cycle.
You can use CodeStudio to practice various DSA questions typically asked in interviews of your placements. It will help you in acquring efficient coding techniques.