Practical 1- Write a program to implement Abstract Data Types (ADT)

ADT includes 3 data types namely

1) STACK 2) LIST 3) QUEUE we will see programs on each of this ADT’s
-------------------------------------------------------------------------------------------------------------
PROGRAM 1A) STACK ADT
# Python program for implementation of stack
# import maxsize from sys module
# Used to return -infinite when stack is empty

from sys import maxsize

# Function to create a stack. It initializes size of stack as 0
def createStack():
stack = []
return stack

# Stack is empty when stack size is 0

def isEmpty(stack):
return len(stack) == 0

# Function to add an item to stack. It increases size by 1

def push(stack, item):
stack.append(item)
print(item + " pushed to stack ")

# Function to remove an item from stack. It decreases size by 1

def pop(stack):
if (isEmpty(stack)):
return str(-maxsize -1) # return minus infinite

return stack.pop()

# Function to return the top from stack without removing it

def peek(stack):
if (isEmpty(stack)):
return str(-maxsize -1) # return minus infinite
return stack[len(stack) - 1]

# Driver program to test above functions

stack = createStack()
push(stack, str(10))
push(stack, str(20))
push(stack, str(30))
print(pop(stack) + " popped from stack")

Output-
Explanation About important methods used in above program:
Sr.no Method name Explanation

1 pop () Used to remove element from stack.

2 Push() Used to add element into the stack.

3 Peek() Used to return top of the stack without removing it.
4 append() Used to add values to the last part of stack
5 deque() A double-ended queue, or deque, has the feature of adding
and removing elements from either end.

Point to Remember:
------🡪
● Note: you can’t remove any element from empty stack you will receive stack
underflow Exception.
● You can’t add any element if stack is already full if you do so , you will receive stack
overflow Exception.
-------------------------------------------------------------------------------------------------------------
Program 1A1) STACK ADT USING LIST
# Python program to demonstrate stack implementation using list
stack = []

# append() function to push

# element in the stack
stack.append('a')
stack.append('b')
stack.append('c')

print('Initial stack')
print(stack)

# pop() function to pop

# element from stack in
# LIFO order
print('\nElements popped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())

print('\nStack after elements are popped:')

print(stack)

# uncommenting print(stack.pop())
# will cause an IndexError
# as the stack is now empty

OUTPUT:
You can implement stack with deque , queue and singly linked List .
Program 1A.2)
# Python program to demonstrate stack implementation using collections.deque

from collections import deque

stack = deque()

# append() function to push

# element in the stack
stack.append('a')
stack.append('b')
stack.append('c')

print('Initial stack:')
print(stack)

# pop() function to pop

# element from stack in
# LIFO order
print('\nElements popped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())

print('\nStack after elements are popped:')

print(stack)

# uncommenting print(stack.pop())
# will cause an IndexError
# as the stack is now empty
OUTPUT:
-------------------------------------------------------------------------------------------------------------
PROGRAM 1.A.3 STACK Implementation using queue
#Python program to demonstrate stack implementation using queue module

from queue import LifoQueue

# Initializing a stack
stack = LifoQueue(maxsize=3)

# qsize() show the number of elements

# in the stack
print(stack.qsize())

# put() function to push

# element in the stack
stack.put('a')
stack.put('b')
stack.put('c')

print("Full: ", stack.full())

print("Size: ", stack.qsize())

# get() function to pop

# element from stack in
# LIFO order
print('\nElements popped from the stack')
print(stack.get())
print(stack.get())
print(stack.get())

print("\nEmpty: ", stack.empty())

OUTPUT:
Functions available in queue module
● maxsize – Number of items allowed in the queue.
● empty() – Return True if the queue is empty, False otherwise.
● full() – Return True if there are maxsize items in the queue. If the queue was initialized with
maxsize=0 (the default), then full() never returns True.
● get() – Remove and return an item from the queue. If the queue is empty, wait until an item is
available.
● get_nowait() – Return an item if one is immediately available, else raise QueueEmpty.
● put(item) – Put an item into the queue. If the queue is full, wait until a free slot is available
before adding the item.
● put_nowait(item) – Put an item into the queue without blocking. If no free slot is immediately
available, raise QueueFull.
● qsize() – Return the number of items in the queue.

PROGRAM 1A4)
Implementation STACK ADT using a singly linked list
# Python program to demonstrate stack implementation using a linked list.
# node class

class Node:
def init (self, value):
self.value = value
self.next = None

class Stack:
# Initializing a stack.
# Use a dummy node, which is #
easier for handling edge cases.
def init (self):
self.head = Node("head")
self.size = 0
# String representation of the stack
def str (self):
cur = self.head.next
out = ""
while cur:
out += str(cur.value) + "->"
cur = cur.next
return out[:-3]
# Get the current size of the stack
def getSize(self):
return self.size

# Check if the stack is empty

def isEmpty(self):
return self.size == 0

# Get the top item of the stack

def peek(self):

# Sanitary check to see if we

# are peeking an empty stack.
if self.isEmpty():
raise Exception("Peeking from an empty stack")
return self.head.next.value

# Push a value into the stack.

def push(self, value):
 node = Node(value)
node.next = self.head.next
self.head.next = node
self.size += 1

# Remove a value from the stack and return.

def pop(self):
if self.isEmpty():
raise Exception("Popping from an empty stack")
remove = self.head.next
self.head.next = self.head.next.next
self.size -= 1
return remove.value

# Driver Code
if name == " main ":
stack = Stack()
for i in range(1, 11):
stack.push(i)
print(f"Stack: {stack}")

for _ in range(1, 6):

remove = stack.pop()
print(f"Pop: {remove}")
print(f"Stack: {stack}")

OUTPUT:

Methods :
The linked list has two methods addHead(item) and removeHead() that run in constant time.
These two methods are suitable to implement a stack.
● getSize()– Get the number of items in the stack.
● isEmpty() – Return True if the stack is empty, False otherwise.
● peek() – Return the top item in the stack. If the stack is empty, raise an exception.
● push(value) – Push a value into the head of the stack.
● pop() – Remove and return a value in the head of the stack. If the stack is empty, raise an
exception.
Program 1B QUEUE ADT
# Python program to demonstrate queue implementation using list

# Initializing a queue
queue = []

# Adding elements to the queue

queue.append('a')
queue.append('b')
queue.append('c')

print("Initial queue")
print(queue)

# Removing elements from the queue

print("\nElements dequeued from queue")
print(queue.pop(0))
print(queue.pop(0))
print(queue.pop(0))

print("\nQueue after removing elements")

print(queue)
# Uncommenting print(queue.pop(0))
# will raise and IndexError
# as the queue is now empty

OUTPUT:

METHODS USED:
● Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow
condition – Time Complexity : O(1)
● Dequeue: Removes an item from the queue. The items are popped in the same order in which
they are pushed. If the queue is empty, then it is said to be an Underflow condition – Time
Complexity : O(1)
● Front: Get the front item from queue – Time Complexity : O(1)
● Rear: Get the last item from queue – Time Complexity : O(1)

-------------------------------------------------------------------------------------------------------------
PROGRAM 1C: implementation of LIST ADT.
# Declaring a list with integer and string elements
list = [10, 20, 30, "New Delhi", "Mumbai"]

# printing list
print("List elements are: ", list)

# adding elements
list.append (40)
list.append (50)
list.append ("Chennai")

# printing list after adding elements

print ("List elements: ", list)

# removing elements
list.pop () ;
# printing list
print ("List elements: ", list)
# removing elements
list.pop () ;
# printing list
print ("List elements: ", list)

OUTPUT:

Methods used:
Python List append() Method
It is used to add/append an object (which will be passed in method as parameter) to the list.
Syntax:
list.append(element)
Here,
● list - is the name of the list.
● append() - is the method name, that is used to add element/object to the list.
● element - is an element (which is considered as on object or element) to be added in the list.
Python List pop() Method
It is used to remove/pop an object from the list.
Syntax:
list.pop()
Here,
● list is the name of the list.
● pop() is the method name that is used to remove last element from the list.
Practical 2-Write a program to implement Singly Linked list with insertion, deletion, traversal
operations .
Practical 2(A)-Write a program to implement singly linked list with insertion
# A complete working Python program to demonstrate all insertion methods of linked list

# Node class
class Node:

# Function to initialise the node object

def init (self, data):
self.data = data # Assign data
self.next = None # Initialize next as null

# Linked List class contains a Node object

class LinkedList:

# Function to initialize head

def init (self):
self.head = None

# Function to insert a new node at the beginning

def push(self, new_data):

# 1 & 2: Allocate the Node &

# Put in the data
new_node = Node(new_data)

# 3. Make next of new Node as head

new_node.next = self.head

# 4. Move the head to point to new Node

self.head = new_node

# This function is in LinkedList class. Inserts a

# new node after the given prev_node. This method is
# defined inside LinkedList class shown above */
def insertAfter(self, prev_node, new_data):

# 1. check if the given prev_node exists

if prev_node is None:
print("The given previous node must inLinkedList.")
return

# 2. create new node

&# Put in the data
new_node = Node(new_data)

# 4. Make next of new Node as next of prev_node

new_node.next = prev_node.next

# 5. make next of prev_node as new_node

prev_node.next = new_node

# This function is defined in Linked List class

 # Appends a new node at the end. This method is
# defined inside LinkedList class shown above */
def append(self, new_data):

# 1. Create a new node

# 2. Put in the data
# 3. Set next as None
new_node = Node(new_data)

# 4. If the Linked List is empty, then make the

# new node as head
if self.head is None:
self.head = new_node
return

# 5. Else traverse till the last node

last = self.head
while (last.next):
last = last.next

# 6. Change the next of last node

last.next = new_node

# Utility function to print the linked list

def printList(self):
temp = self.head
while (temp):
print(temp.data,end=" ")
temp = temp.next

# Code execution starts here

if name ==' main ':

# Start with the empty list

llist = LinkedList()

# Insert 6. So linked list becomes 6->None

llist.append(6)

# Insert 7 at the beginning. So linked list becomes 7->6->None

llist.push(7);

# Insert 1 at the beginning. So linked list becomes 1->7->6->None

llist.push(1);

# Insert 4 at the end. So linked list becomes 1->7->6->4->None

llist.append(4)

# Insert 8, after 7. So linked list becomes 1 -> 7-> 8-> 6-> 4-> None
llist.insertAfter(llist.head.next, 8)

print('Created linked list is: ')

llist.printList()

Output-
Practical 2(B)- write a program to implement singly linked list with deletion
# A complete working Python3 program to
# demonstrate deletion in singly
# linked list with class

# Node class
class Node:

# Constructor to initialize the node object

def init (self, data):
self.data = data
self.next = None

class LinkedList:

# Function to initialize head

def init (self):
self.head = None

# Function to insert a new node at the beginning

def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node

# Given a reference to the head of a list and a key,

# delete the first occurrence of key in linked list
def deleteNode(self, key):

# Store head node

temp = self.head

# If head node itself holds the key to be deleted

if (temp is not None):
if (temp.data == key):
self.head = temp.next
temp = None
return

# Search for the key to be deleted, keep track of the

# previous node as we need to change 'prev.next'
while(temp is not None):
if temp.data == key:
break
prev = temp
temp = temp.next

# if key was not present in linked list

if(temp == None):
return

# Unlink the node from linked list

 prev.next = temp.next

temp = None

# Utility function to print the linked LinkedList

def printList(self):
temp = self.head
while(temp):
print (" %d" %(temp.data)),
temp = temp.next

# Driver program
llist = LinkedList()
llist.push(7)
llist.push(1)
llist.push(3)
llist.push(2)

print ("Created Linked List: ")

llist.printList()
llist.deleteNode(1)
print ("\nLinked List after Deletion of 1:")
llist.printList()

Output-

Practical 2(C)-Write a program to implement singly linked list with traversal

# Python 3 program to find the middle of a
# given linked list

# Node class
class Node:

# Function to initialise the node object

def init (self, data):
self.data = data
self.next = None

class LinkedList:

def init (self):

self.head = None

def push(self, new_data):

 new_node = Node(new_data)
new_node.next = self.head
self.head = new_node

# Function to get the middle of

# the linked list
def printMiddle(self):
slow_ptr = self.head
fast_ptr = self.head

if self.head is not None:

while (fast_ptr is not None and fast_ptr.next is not None):
fast_ptr = fast_ptr.next.next
slow_ptr = slow_ptr.next
print("The middle element is: ", slow_ptr.data)

# Driver code
list1 = LinkedList()
list1.push(5)
list1.push(4)
list1.push(2)
list1.push(3)
list1.push(1)
list1.printMiddle()
Output-

Methods used:
● insert(): Add an item to the linked list at the head of the list
● find(): Find an item within the linked list
● remove(): Remove a given item with a given value
● is_empty(): Returns whether the linked list is empty or not
● get_count(): Returns the number of items in the linked list
● deleteAt(index): delete an item at a given index
● findAt(index): find the item at the given index
● insertAt(index): insert an item at a given index
Practical 3-Write a program to implement Doubly Linked list with insertion, deletion, traversal
operations
Practical 3(A)- Write a program to implement doubly linked list with insertion.
# Create the Node class
class Node:
def init (self, data):
self.data = data
self.next = None
self.prev = None

# Create the doubly linked list

class doubly_linked_list:
def init (self):
self.head = None

# Define the push method to add elements

def push(self, NewVal):
NewNode = Node(NewVal)
NewNode.next = self.head
if self.head is not None:
self.head.prev = NewNode
self.head = NewNode

# Define the insert method to insert the element

def insert(self, prev_node, NewVal):
if prev_node is None:
return
NewNode = Node(NewVal)
NewNode.next = prev_node.next
prev_node.next = NewNode
NewNode.prev = prev_node
if NewNode.next is not None:
NewNode.next.prev = NewNode

# Define the method to print the linked list

def listprint(self, node):
while (node is not None):
print(node.data),
last = node
node = node.next

dllist = doubly_linked_list()
dllist.push(12)
dllist.push(8)
dllist.push(62)
dllist.insert(dllist.head.next, 13)
dllist.listprint(dllist.head)

Output-
Practical 3(B)-Write a program to implement doubly linked list with deletion
# Program to delete a node in a doubly-linked list For Garbage collection
import gc

# A node of the doubly linked list

class Node:

# Constructor to create a new node

def init (self, data):
self.data = data
self.next = None
self.prev = None

class DoublyLinkedList:

# Constructor for empty Doubly

# Linked List
def init (self):
self.head = None

# Function to delete a node in a Doubly

# Linked List. head_ref --> pointer to
# head node pointer. dele --> pointer to
# node to be deleted.
def deleteNode(self, dele):

# Base Case
if self.head is None or dele is None:
return

# If node to be deleted is head node

if self.head == dele:
self.head = dele.next

# Change next only if node to be

# deleted is NOT the last node
if dele.next is not None:
dele.next.prev = dele.prev

# Change prev only if node to be

# deleted is NOT the first node
if dele.prev is not None:
dele.prev.next = dele.next

# Finally, free the memory occupied

# by dele
# Call python garbage collector
gc.collect()

# Given a reference to the head of a

# list and an integer, inserts a new
# node on the front of list
def push(self, new_data):

# 1. Allocates node
# 2. Put the data in it
new_node = Node(new_data)
 # 3. Make next of new node as head
# and previous as None (already None)
new_node.next = self.head

# 4. Change prev of head node to

# new_node
if self.head is not None:
self.head.prev = new_node

# 5. Move the head to point to the

# new node
self.head = new_node

def printList(self, node):

while(node is not None):
print node.data,
node = node.next

# Driver code
# Start with empty list
dll = DoublyLinkedList()

# Let us create the doubly linked list

# 10<->8<->4<->2
dll.push(2);
dll.push(4);
dll.push(8);
dll.push(10);

print "Original Linked List",

dll.printList(dll.head)

# Delete nodes from doubly linked list

dll.deleteNode(dll.head)
dll.deleteNode(dll.head.next)
dll.deleteNode(dll.head.next)

# Modified linked list will be NULL<-8->NULL

print "Modified Linked List",
dll.printList(dll.head)

Output-

Practical 3( C )- Traversal operation in doubly linked list

class Node:
def init (self, data):
self.item = data
self.nref = None
 self.pref = None

class DoublyLinkedList:
def init (self):
 self.start_node = None

def insert_in_emptylist(self, data):

if self.start_node is None:
new_node = Node(data)
self.start_node = new_node
else:
print("list is not empty")

def insert_at_start(self, data):

if self.start_node is None:
new_node = Node(data)
self.start_node = new_node
print("node inserted")
return
new_node = Node(data)
new_node.nref = self.start_node
self.start_node.pref = new_node
self.start_node = new_node

def insert_at_end(self, data):

if self.start_node is None:
new_node = Node(data)
self.start_node = new_node
return
n = self.start_node
while n.nref is not None:
n = n.nref
new_node = Node(data)
n.nref = new_node
new_node.pref = n
def insert_after_item(self, x, data):
if self.start_node is None:
print("List is empty")
return
else:
n = self.start_node
while n is not None:
if n.item == x:
break
n = n.nref
if n is None:
print("item not in the list")
else:
new_node = Node(data)
new_node.pref = n
new_node.nref = n.nref
if n.nref is not None:
n.nref.prev = new_node
n.nref = new_node
def insert_before_item(self, x, data):
if self.start_node is None:
print("List is empty")
return
else:
n = self.start_node
while n is not None:
if n.item == x:
 break
n = n.nref
if n is None:
print("item not in the list")
else:
new_node = Node(data)
new_node.nref = n
new_node.pref = n.pref
if n.pref is not None:
n.pref.nref = new_node
n.pref = new_node

def traverse_list(self):
if self.start_node is None:
print("List has no element")
return
else:
n = self.start_node
while n is not None:
print(n.item , " ")
n = n.nref
OUTPUT:
Practical 4-Write a program to implement Stack with insertion, deletion, traversal operations
# Python program to
# demonstrate stack implementation
# using collections.deque

from collections import deque

stack = deque()

# append() function to push

# element in the stack
stack.append('a')
stack.append('b')
stack.append('c')

print('Initial stack:')
print(stack)

# pop() function to pop

# element from stack in
# LIFO order
print('\nElements popped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())

print('\nStack after elements are popped:')

print(stack)

# uncommenting print(stack.pop())
# will cause an IndexError
# as the stack is now empty
Output-
Practical 5-Write a program to implement Queue with insertion, deletion, traversal
operations.

# Python program to
# demonstrate queue implementation
# using list

# Initializing a queue
queue = []

# Adding elements to the queue

queue.append('a')
queue.append('b')
queue.append('c')

print("Initial queue")
print(queue)

# Removing elements from the queue

print("\nElements dequeued from queue")
print(queue.pop(0))
print(queue.pop(0))
print(queue.pop(0))

print("\nQueue after removing elements")

print(queue)

# Uncommenting print(queue.pop(0))
# will raise and IndexError
# as the queue is now empty

Output-
Practical 6-Write a program to implement Priority Queue with insertion, deletion, traversal
operations

# Python3 code to implement Priority Queue

# using Singly Linked List

# Class to create new node which includes

# Node Data, and Node Priority
class PriorityQueueNode:

def init (self, value, pr):

self.data = value
self.priority = pr
self.next = None

# Implementation of Priority Queue

class PriorityQueue:

def init (self):

self.front = None

# Method to check Priority Queue is Empty

# or not if Empty then it will return True
# Otherwise False
def isEmpty(self):
return True if self.front == None else False
# Method to add items in Priority Queue
# According to their priority value
def push(self, value, priority):

# Condition check for checking Priority

# Queue is empty or not
if self.isEmpty() == True:

# Creating a new node and assigning

# it to class variable
self.front = PriorityQueueNode(value,priority)

# Returning 1 for successful execution

return 1

else:

# Special condition check to see that

# first node priority value
if self.front.priority > priority:

# Creating a new node

newNode = PriorityQueueNode(value,priority)

# Updating the new node next value

newNode.next = self.front

# Assigning it to self.front
self.front = newNode

# Returning 1 for successful execution

return 1
 else:

# Traversing through Queue until it

# finds the next smaller priority node
temp = self.front

while temp.next:

# If same priority node found then current

# node will come after previous node
if priority <= temp.next.priority:
break

temp = temp.next

newNode = PriorityQueueNode(value,priority)
newNode.next = temp.next
temp.next = newNode

# Returning 1 for successful execution

return 1

# Method to remove high priority item

# from the Priority Queue
def pop(self):

# Condition check for checking

# Priority Queue is empty or not
if self.isEmpty() == True:
return

else:

# Removing high priority node from

# Priority Queue, and updating front
# with next node
self.front = self.front.next
return 1

# Method to return high priority node

# value Not removing it
def peek(self):

# Condition check for checking Priority

# Queue is empty or not
if self.isEmpty() == True:
return
else:
return self.front.data

# Method to Traverse through Priority

# Queue
def traverse(self):

# Condition check for checking Priority

# Queue is empty or not
if self.isEmpty() == True: return
"Queue is Empty!"
else:
temp = self.front
while temp:
 print(temp.data, end = " ")
temp = temp.next

# Driver code
if name == " main ":

# Creating an instance of Priority

# Queue, and adding values
# 7 -> 4 -> 5 -> 6
pq = PriorityQueue()
pq.push(4, 1)
pq.push(5, 2)
pq.push(6, 3)
pq.push(7, 0)

# Traversing through Priority Queue

pq.traverse()

# Removing highest Priority item

# for priority queue
pq.pop()

Output-
Practical 7- Write a program to implement Binary Tree with insertion, deletion, traversal
operations
Practical 7(A)- BST with insertion
class Tree:

def init (node, value):

node.value = value
node.left = None
node.right = None

def Inorder( node, Root ):

if( Root is None ):
return
node.Inorder(Root.left)
print(Root.value,end = ' ')
node.Inorder(Root.right)

def Insert(node, value):

if node is None:
node = Tree(value)
elif value < node.value:
if node.left is None:
node.left = Tree(value)
else:
node.left.Insert(value)
else:
if node.right is None:
node.right = Tree(value)
else:
node.right.Insert(value)
Root = Tree(6)
Root.Insert(4)
Root.Insert(2)
Root.Insert(5)
Root.Insert(9)
Root.Insert(8)
Root.Insert( 10)
print ("Inorder traversal after insertion: ",end = '')
Root.Inorder(Root)

Output-

Practical 7(B)-BST with deletion

class Tree:

def init (node, value):

node.value = value
node.left = None
node.right = None

def Inorder( node, Root ):

if( Root is None ):
return
node.Inorder(Root.left)
print(Root.value,end = ' ')
node.Inorder(Root.right)

def Insert(node, value):

 if node is None:
node = Tree(value)
elif value < node.value:
if node.left is None:
node.left = Tree(value)
else:
node.left.Insert(value)
else:
if node.right is None:
node.right = Tree(value)
else:
node.right.Insert(value)
def Delete(node,temp, value):
if value < node.value:
temp = node
node.left.Delete(temp,value)
elif(value > node.value):
temp = node
node.right.Delete(temp, value)

else:
if (node.left is None and node.right is None):
if(temp.left == node):
temp.left = None
else:
temp.right = None
node = None

elif node.right is None :

if(temp.left == node):
temp.left = node.left
else:
temp.right = node.left
node = None

elif node.left is None :

if(temp.left == node):
temp.left = node.right
else:
temp.right = node.right
node = None

else:
temp = node.right
while(temp.left is not None):
temp = temp.left
node.value = temp.value
node.right.Delete(temp,temp.value)
Root = Tree(6)
Root.Insert(4)
Root.Insert(2)
Root.Insert(5)
Root.Insert(9)
Root.Insert(8)
Root.Insert( 10)

print ("Inorder traversal after insertion: ",end = '')

Root.Inorder(Root)
Root.Delete(Root, 2)
print ('\n 2 is deleted: ',end ='')
Root.Inorder(Root)
Root.Delete(Root, 4)
print ('\n 4 is deleted: ',end ='')
Root.Inorder(Root)

Root.Delete(Root, 6)
print ('\n 6 is deleted: ',end ='')
Root.Inorder(Root)

Output-

Practical 7(C)- BST with traversal

# Python program to for tree traversals

# A class that represents an individual node in a

# Binary Tree

class Node:
def init (self, key):
self.left = None
self.right = None
self.val = key

# A function to do inorder tree traversal

def printInorder(root):

if root:

# First recur on left child

printInorder(root.left)

# then print the data of node

print(root.val),

# now recur on right child

printInorder(root.right)

# A function to do postorder tree traversal

def printPostorder(root):

if root:

# First recur on left child

printPostorder(root.left)

# the recur on right child

printPostorder(root.right)
 # now print the data of node
print(root.val),

# A function to do preorder tree traversal

def printPreorder(root):

if root:

# First print the data of node

print(root.val),

# Then recur on left child

printPreorder(root.left)

# Finally recur on right child

printPreorder(root.right)

# Driver code
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print ("Preorder traversal of binary tree is")
printPreorder(root)

print ("\nInorder traversal of binary tree is")

printInorder(root)

print ("\nPostorder traversal of binary tree is")

printPostorder(root)
Practical 8-Write a Program to implement Huffman Coding.

from collections import Counter

class NodeTree(object):
def init__(self, left=None, right=None):
self.left = left
self.right = right

def children(self):
return self.left, self.right

def str (self):

return self.left, self.right

def huffman_code_tree(node, binString=''):

'''
Function to find Huffman Code
'''
if type(node) is str:
return {node: binString}
(l, r) = node.children()
d = dict()
d.update(huffman_code_tree(l, binString + '0'))
d.update(huffman_code_tree(r, binString + '1'))
return d

def make_tree(nodes):
'''
Function to make tree
:param nodes: Nodes
:return: Root of the tree
'''
while len(nodes) > 1:
(key1, c1) = nodes[-1]
(key2, c2) = nodes[-2]
nodes = nodes[:-2]
node = NodeTree(key1, key2)
nodes.append((node, c1 +
c2))
nodes = sorted(nodes, key=lambda x: x[1], reverse=True)
return nodes[0][0]

if name == ' main ':

string = 'BCAADDDCCACACAC'
freq = dict(Counter(string))
freq = sorted(freq.items(), key=lambda x: x[1], reverse=True)
node = make_tree(freq)
encoding = huffman_code_tree(node)
for i in encoding:
print(f'{i} : {encoding[i]}')
Output-

What is Huffman coding?

Huffman coding is a lossless data compression algorithm. The idea is to assign
variable-length codes to input characters, lengths of the assigned codes are based on the
frequencies of corresponding characters. The most frequent character gets the smallest
code and the least frequent character gets the
largest code. The variable-length codes assigned to input
characters are Prefix Codes, means the codes (bit sequences) are assigned in such a way
that the code assigned to one character is not the prefix of code assigned to any other
character. This is how Huffman Coding makes sure that there is no
ambiguity when decoding thegenerated bitstream. Let us understand prefix
codes with a counter example. Let there be four characters a, b, c and d, and their
corresponding variable length codes be 00, 01, 0 and 1. This coding leads to ambiguity
because code assigned to c is the prefix of codes assigned to a and b. If the compressed bit
stream is 0001, the de-compressed output may be “cccd” or “ccb” or “acd” or “ab”.
There are mainly two major parts in Huffman Coding
1. Build a Huffman Tree from input characters.
2. Traverse the Huffman Tree and assign codes to characters.

-------------------------------------------------------------------------------------------------------------
Practical 9-Write a program to implement Graph with insertion, deletion, traversal

operations. # BFS algorithm in Python

import collections

# BFS algorithm
def bfs(graph, root):

visited, queue = set(), collections.deque([root])

visited.add(root)

while queue:

# Dequeue a vertex from queue

vertex = queue.popleft()
print(str(vertex) + " ", end="")

# If not visited, mark it as visited, and

# enqueue it
for neighbour in graph[vertex]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)

if name == ' main ':

graph = {0: [1, 2], 1: [2], 2: [3], 3: [1, 2]}
print("Following is Breadth First Traversal: ")
 bfs(graph, 0)

Output-

-------------------------------------------------------------------------------------------------------------
Practical 10-
Write a program to implement Travelling Salesman Problem.
------------------------------------------------------------------------------------------------------------
Travelling Salesman Problem
Travelling Sales Person Problem
The traveling salesman problems abide by a salesman and a set of cities. The salesman has to visit
every one of the cities starting from a certain one (e.g., the hometown) and to return to the same city.
The challenge of the problem is that the traveling salesman needs to minimize the total length of the
trip.
Suppose the cities are x1 x2 xn where cost cij denotes the cost of travelling from city xi to xj. The
travelling salesperson problem is to find a route starting and ending at x1 that will take in all cities with
the minimum cost.
Example: A newspaper agent daily drops the newspaper to the area assigned in such a manner that
he has to cover all the houses in the respective area with minimum travel cost. Compute the minimum
travel cost.
# Python3 program to implement traveling salesman
# problem using naive approach.

from sys import maxsize

from itertools import permutations
V=4

# implementation of traveling Salesman Problem

def travellingSalesmanProblem(graph, s):

# store all vertex apart from source vertex

vertex = []
for i in range(V):
if i != s:
vertex.append(i)

# store minimum weight Hamiltonian Cycle

min_path = maxsize
next_permutation=permutations(vertex)
for i in next_permutation:

# store current Path weight(cost)

current_pathweight = 0

# compute current path weight

k=s
for j in i:
 current_pathweight += graph[k][j]
k=j
current_pathweight += graph[k][s]

# update minimum
min_path = min(min_path, current_pathweight)
 return min_path

# Driver Code
if name == " main ":

# matrix representation of graph

graph = [[0, 10, 15, 20], [10, 0, 35, 25],
[15, 35, 0, 30], [20, 25, 30, 0]]
s=0
print(travellingSalesmanProblem(graph, s))

Output-
-------------------------------------------------------------------------------------------------------------
Practical 11-Write a program to create basic Hash Table for insertion, deletion, traversal
operations(assume that there are no collisions)
# Python program to demonstrate working of HashTable

hashTable = [[],] * 10
# Python program to demonstrate working of HashTable

hashTable = [[],] * 10

def checkPrime(n):
if n == 1 or n == 0:
return 0

for i in range(2, n//2):

if n % i == 0:
return 0

return 1

def getPrime(n):
if n % 2 == 0:
n=n+1

while not checkPrime(n):

n += 2

return n

def hashFunction(key):
capacity = getPrime(10)
return key % capacity

def insertData(key, data):

index = hashFunction(key)
hashTable[index] = [key, data]

def removeData(key):
index = hashFunction(key)
hashTable[index] = 0

insertData(123, "apple")
insertData(432, "mango")
insertData(213, "banana")
insertData(654, "guava")

print(hashTable)

removeData(123)

print(hashTable)

Output-
Practical 12-Write a program to create hash table to handle collisions using overflow
chaining.

# Function to display hashtable

def display_hash(hashTable):

for i in range(len(hashTable)):
print(i, end = " ")

for j in hashTable[i]:
print("-->", end = " ")
print(j, end = " ")

print()

# Creating Hashtable as
# a nested list.
HashTable = [[] for _ in range(10)]

# Hashing Function to return

# key for every value.
def Hashing(keyvalue):
return keyvalue % len(HashTable)

# Insert Function to add

# values to the hash table
def insert(Hashtable, keyvalue, value):

hash_key = Hashing(keyvalue)
Hashtable[hash_key].append(value)

# Driver Code
insert(HashTable, 10, 'Allahabad')
insert(HashTable, 25, 'Mumbai')
insert(HashTable, 20, 'Mathura')
insert(HashTable, 9, 'Delhi')
insert(HashTable, 21, 'Punjab')
insert(HashTable, 21, 'Noida')

display_hash (HashTable)

Output-