# Implementing basic Data Structures in Python — Part 2| Daily Python #16

This article is a tutorial that covers the implementation of basic data structures — Graphs and Trees. This article is in continuation with Daily Python #12, which covers — LinkedList, Stack, and Queue.

This article is a part of Daily Python challenge that I have taken up for myself. I will be writing short python articles daily.

There are no additional requirements for this article.

# Graphs

A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph. Formally a Graph can be defined as —* A Graph consists of a finite set of vertices(or nodes) and set of Edges that connect a pair of nodes.*

## Two most commonly used representations of Graphs:

- Adjacency Matrix
- Adjacency List

*We will cover both of these representations in this article.*

## Adjacency Matrix

It is a 2D array of size V x V where V is the number of vertices in a graph.

Let the 2D array be matrix[][], a slot **matrix[i][j] = 1** indicates that there is an edge from vertex i to vertex j.

The adjacency matrix for an undirected graph is always symmetric.

Adjacency Matrix is also used to represent weighted graphs. If matrix[i][j] = w, then there is an edge from vertex i to vertex j with weight w.

## Adjacency List

An array of lists is used. The size of the array is equal to the number of vertices. Let the array be an array[]. An entry array[i] represents the list of vertices adjacent to the** i**th vertex. This representation can also be used to represent a weighted graph. The weights of edges can be represented as lists of pairs.

Following is the adjacency list representation of the above graph.

## Let’s define a class Graph that will implement both of the above representations

class Graph: def __init__(self,totalNodes):

self.totalNodes = totalNodes

self.adjMatrix = []

self.adjList = [] def acceptAdjMatrix(self):

print('The total number of nodes : ',self.totalNodes)

for row in range(self.totalNodes):

temp = list(map(int,input('Enter Row ' +str(row)+' of matrix : ').split(' ')))

self.adjMatrix.append(temp)

def printAdjMatrix(self):

if len(self.adjMatrix) == 0:

print('Please fill the Adjacency Matrix')

return

print('Given Adjacency Matrix :')

for row in self.adjMatrix:

print(row) def acceptAdjList(self):

print('The total number of nodes : ',self.totalNodes)

print('Nodes : ',list(range(self.totalNodes)))

for node in range(self.totalNodes):

temp = list(map(int,input('Enter Adjacent Nodes of Node' +str(node)+' : ').split(' ')))

self.adjList.append(temp) def printAdjList(self):

if len(self.adjList) == 0:

print('Please fill the Adjacency List')

return

print('\n\nGiven Adjacency List :')

for i in range(self.totalNodes):

print(i,end='--> ')

for j in self.adjList[i]:

print(j,end=' ')

print('')

The above code snippet has the basic functions of accepting the Adjacency Matrix and the Adjacency List, and also printing these two representations.

`graph = Graph(5)`

graph.acceptAdjMatrix()

graph.printAdjMatrix()

graph.acceptAdjList()

graph.printAdjList()

There are multiple ways to traverse the graphs, one such method is **Breadth-First Search Traversal**

` def BFS(self):`

iterator = 0

queue = [iterator]

visited = [0]*self.totalNodes

visited[iterator] = 1

while len(queue)>0:

queue.extend([ node for node in self.adjList[iterator] if visited[node] != 1 and node not in queue])

print(queue[0],end=' ')

visited[iterator] = 1

iterator = queue[0]

queue = queue[1:]

print('')

# Trees

A **tree** is a widely used abstract data type (ADT) that simulates a hierarchical tree structure, with a root value and sub-trees of children with a parent node, represented as a set of linked nodes.

A tree data structure can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the “children”), with the constraints that no reference is duplicated, and none points to the root.

The most common representation of a tree is the Binary Search Tree

**Binary Search Tree** is a node-based binary tree data structure which has the following properties:

- The left subtree of a node contains only nodes with keys lesser than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- The left and right subtree each must also be a binary search tree.

## Let’s define a class for a simple Node that will be the basic element of the tree

`class Node:`

def __init__(self,value):

self.value = value

self.rightNode = None

self.leftNode = None

## Let’s define a class for the Binary Search Tree

class BSTree: def __init__(self):

self.headNode = None def insertNode(self,value):

node = Node(value)

if self.headNode == None:

self.headNode = node

print(value,' inserted successfully') else:

iterator = self.headNode

while True:

if value < iterator.value:

if iterator.leftNode == None:

iterator.leftNode = node

break

else:

iterator = iterator.leftNode

else:

if iterator.rightNode == None:

iterator.rightNode = node

break

else:

iterator = iterator.rightNode

print(value,' inserted successfully') def printTree(self):

print('\n\nPreOrder Traversal (Root, Left, Right)')

self.preOrder(self.headNode)

print('\n\nInOrder Traversal (Left, Root, Right)')

self.inOrder(self.headNode)

print('\n\nPostOrder Traversal (Left, Right, Root)')

self.postOrder(self.headNode)

def inOrder(self,node):

if node == None:

return

self.inOrder(node.leftNode)

print(node.value, end=' ')

self.inOrder(node.rightNode) def preOrder(self,node):

if node == None:

return

print(node.value, end=' ')

self.preOrder(node.leftNode)

self.preOrder(node.rightNode) def postOrder(self,node):

if node == None:

return

self.postOrder(node.leftNode)

self.postOrder(node.rightNode)

print(node.value, end=' ')

## Depth First Traversals:

1. Inorder (Left, Root, Right)

2. Preorder (Root, Left, Right)

3. Postorder (Left, Right, Root)

## Let’s test the above code by inserting few values in the tree and traverse it

`tree = BSTree()`

tree.insertNode(5)

tree.insertNode(3)

tree.insertNode(1)

tree.insertNode(4)

tree.insertNode(6)

tree.printTree()

*I hope this article was helpful, do leave some claps if you liked it.*