DAV Institute of Engineering and Technology

Advance Data Structure

Practical File

Submitted to :- Submitted by :-
Mrs. Archana Aggarwal Ritu
MCA sem-1
Regd. No. : 30210/22
[Link] a Python program to create an array of 5 elements and
display the array items. Access each individual element through
indexes.
Ans.
arr=[]
print('enter elements of array:')
for x in range(0,5):
y=int(input(''))
[Link](y)
print('elements are:')
print(arr)
for x in range(0,len(arr)) :
print("arr[{}]=".format(x),arr[x])
Output:-

1|Page
[Link] a Python program to reverse the order of the items in
the array.
Ans.
arr=[]
print('enter elements of array:')
for x in range(0,5):
y=int(input(''))
[Link](y)
for x in range(len(arr)-1,-1,-1) :
print("arr[{}]=".format(x),arr[x])
Output:-

2|Page
[Link] a Python program to append a new item to the end of
the array.
Ans.
arr=[]
print('enter elements of array:')
for x in range(0,5):
y=int(input(''))
[Link](y)
print('elements are:')
print(arr)
z=int(input("enter element you want to append= "))
print("append {} at the end".format(z))
[Link](z)
print("New array:",arr)
Output:-

3|Page
[Link] a Python program to remove a specified item using the
index from an array.
Ans.
arr=[]
print('enter elements of array:')
for x in range(0,5):
y=int(input(''))
[Link](y)
print('elements are:')
print(arr)
z=int(input("enter element you want to remove= "))
print("remove {} from the end".format(z))
[Link](z)
print("New array:",arr)
Output:-

4|Page
[Link] a Python program to get the length of an array.
Ans.
arr=[]
print('enter elements of array:')
for x in range(0,5):
y=int(input(''))
[Link](y)
print('elements are:')
print(arr)
z=len(arr)
print("length of an array:",z)
Output:-

5|Page
[Link] a python program of linear search.
Ans.
def linearSearch(array, n, x):
# Going through array sequentially
for i in range(0, n):
if (array[i] == x):
return i
return -1
array = [2, 4, 0, 1, 9]
print("the array is ",array)
x = int(input("enter element which you want to search: "))
n = len(array)
result = linearSearch(array, n, x)
if(result == -1):
print("Element not found")
else:
print("Element found at index: ", result)
Output:-

6|Page
Ques7. Write a python program of binary search.
Ans.
Iterative Method
def binarySearch(array, x, low, high):
# Repeat until the pointers low and high meet each other
while low <= high:
mid = low + (high - low)//2
if array[mid] == x:
return mid
elif array[mid] < x:
low = mid + 1
else:
high = mid - 1
return -1
array = [3, 4, 5, 6, 7, 8, 9]
print("the array is ",array)
x = int(input("Enter element which you want search:"))
result = binarySearch(array, x, 0, len(array)-1)
if result != -1:
print("Element is present at index " + str(result))
else:
print("does not exist")
Output:-

7|Page
 Recursive Method
def binarySearch(array, x, low, high):
if high >= low:
mid = low + (high - low)//2
# If found at mid, then return it
if array[mid] == x:
return mid
# Search the left half
elif array[mid] > x:
return binarySearch(array, x, low, mid-1)
# Search the right half
else:
return binarySearch(array, x, mid + 1, high)
else:
return -1
array = [3, 4, 5, 6, 7, 8, 9]
x=4
result = binarySearch(array, x, 0, len(array)-1)
if result != -1:
print("Element is present at index " + str(result))
else:
print("Not found")

8|Page
Output:-

9|Page
[Link] a Python program to sort a list of elements using the
bubble sort algorithm.
Ans.
def bubbleSort(arr):
n = len(arr)
# optimize code, so if the array is already sorted, it doesn't need
# to go through the entire process
swapped = False
# Traverse through all array elements
for i in range(n-1):
# range(n) also work but outer loop will
# repeat one time more than needed.
# Last i elements are already in place
for j in range(0, n-i-1):
# traverse the array from 0 to n-i-1
# Swap if the element found is greater
# than the next element
if arr[j] > arr[j + 1]:
swapped = True
arr[j], arr[j + 1] = arr[j + 1], arr[j]
if not swapped:
# if we haven't needed to make a single swap, we
# can just exit the main loop.
return
# Driver code to test above
arr = [64, 34, 25, 12, 22, 11, 90]
print("array is: ",arr)
bubbleSort(arr)

10 | P a g e
print("Sorted array is:")
for i in range(len(arr)):
print("% d" % arr[i], end=" ")
Output:-

11 | P a g e
[Link] a Python program to sort a list of elements using the
selection sort algorithm.
Ans.
#sorting by finding min_index
def selectionSort(array, size):
for ind in range(size):
min_index = ind

for j in range(ind + 1, size):

# select the minimum element in every iteration
if array[j] < array[min_index]:
min_index = j
# swapping the elements to sort the array
(array[ind], array[min_index]) = (array[min_index], array[ind])
arr = [-2, 45, 0, 11, -9,88,-97,-202,747]
print("array is : ",arr)
size = len(arr)
selectionSort(arr, size)
print('The array after sorting in Ascending Order by selection sort is:')
print(arr)
Output:-

12 | P a g e
[Link] a Python program to sort a list of elements using the
insertion sort algorithm.
Ans.
def insertionSort(array):
for step in range(1, len(array)):
key = array[step]
j = step - 1
# Compare key with each element on the left of it until an element
smaller than it is found
# For descending order, change key<array[j] to key>array[j].
while j >= 0 and key < array[j]:
array[j + 1] = array[j]
j=j-1
# Place key at after the element just smaller than it.
array[j + 1] = key

data = [9, 5, 1, 4, 3]
insertionSort(data)
print("the array is ",data)
print('Sorted Array in Ascending Order:')
print(data)
Output:-

13 | P a g e
Ques11. Write a Python program to sort a list of elements using the
quick sort algorithm.
Ans.
# This implementation utilizes pivot as the last element in the nums list
# It has a pointer to keep track of the elements smaller than the pivot
# At the very end of partition() function, the pointer is swapped with the
pivot to come up with a "sorted" nums relative to the pivot
# Function to find the partition position
def partition(array, low, high):
# choose the rightmost element as pivot
pivot = array[high]
# pointer for greater element
i = low - 1
# traverse through all elements
# compare each element with pivot
for j in range(low, high):
if array[j] <= pivot:
# If element smaller than pivot is found
# swap it with the greater element pointed by i
i=i+1
# Swapping element at i with element at j
(array[i], array[j]) = (array[j], array[i])
# Swap the pivot element with the greater element specified by i
(array[i + 1], array[high]) = (array[high], array[i + 1])
# Return the position from where partition is done
return i + 1
# function to perform quicksort
def quickSort(array, low, high):

14 | P a g e
 if low < high:
# Find pivot element such that
# element smaller than pivot are on the left
# element greater than pivot are on the right
pi = partition(array, low, high)
# Recursive call on the left of pivot
quickSort(array, low, pi - 1)
# Recursive call on the right of pivot
quickSort(array, pi + 1, high)
data = [1, 7, 4, 1, 10, 9, -2]
print("Unsorted Array")
print(data)
size = len(data)
quickSort(data, 0, size - 1)
print('Sorted Array in Ascending Order:')
print(data)

Output:-

15 | P a g e
Ques12. Write a Python program to create a singly linked list,
append some items and iterate through the list.
Ans.
class Node:
# Singly linked node
def __init__(self, data=None):
[Link] = data
[Link] = None
class singly_linked_list:
def __init__(self):
# Create an empty list
[Link] = None
[Link] = None
[Link] = 0
def iterate_item(self):
# Iterate the list.
current_item = [Link]
while current_item:
val = current_item.data
current_item = current_item.next
yield val
def append_item(self, data):
#Append items on the list
node = Node(data)
if [Link]:
[Link] = node
[Link] = node
else:

16 | P a g e
 [Link] = node
[Link] = node
[Link] += 1
items = singly_linked_list()
items.append_item('PHP')
items.append_item('Python')
items.append_item('C#')
items.append_item('C++')
items.append_item('Java')
for val in items.iterate_item():
print(val)
print("\[Link]: ",[Link])
print("[Link]: ",[Link])
Output:-

17 | P a g e
Ques13. Write a Python program to find the size of a singly linked
list.
Ans.
class Node:
# Singly linked node
def __init__(self, data=None):
[Link] = data
[Link] = None
class singly_linked_list:
def __init__(self):
# Create an empty list
[Link] = None
[Link] = None
[Link] = 0

def append_item(self, data):

#Append items on the list
node = Node(data)
if [Link]:
[Link] = node
[Link] = node
else:
[Link] = node
[Link] = node
[Link] += 1

def iterate_item(self):
# Iterate the list.

18 | P a g e
 current_item = [Link]
while current_item:
val = current_item.data
current_item = current_item.next
yield val

items = singly_linked_list()
items.append_item('PHP')
items.append_item('Python')
items.append_item('C#')
items.append_item('C++')
items.append_item('Java')

print("Original list:")
for val in items.iterate_item():
print(val)

print("\nSize of the list:",[Link])

Output:-

Ques14. Write a Python program to search a specific item in a

singly linked list and return true if the item is found otherwise
return false.
19 | P a g e
Ans.
class Node:
# Singly linked node
def __init__(self, data=None):
[Link] = data
[Link] = None
class singly_linked_list:
def __init__(self):
# Create an empty list
[Link] = None
[Link] = None
[Link] = 0

def append_item(self, data):

#Append items on the list
node = Node(data)
if [Link]:
[Link] = node
[Link] = node
else:
[Link] = node
[Link] = node
[Link] += 1

def iterate_item(self):
# Iterate the list.
current_item = [Link]
while current_item:
20 | P a g e
 val = current_item.data
current_item = current_item.next
yield val

def search_item(self, val):

# Search the list
for node in self.iterate_item():
if val == node:
return True
return False

items = singly_linked_list()
items.append_item('PHP')
items.append_item('Python')
items.append_item('C#')
items.append_item('C++')
items.append_item('Java')
print("search for item SQL")
if items.search_item('SQL'):
print("True")
else:
print("False")
print("search for item C++")
if items.search_item('C++'):
print("True")
else:
print("False")

21 | P a g e
Output:-

Ques15. Write a Python program to delete the first item from a

singly linked list.
Ans.
class Node:
# Singly linked node
22 | P a g e
 def __init__(self, data=None):
[Link] = data
[Link] = None
class singly_linked_list:
def __init__(self):
# Create an empty list
[Link] = None
[Link] = None
[Link] = 0

def append_item(self, data):

#Append items on the list
node = Node(data)
if [Link]:
[Link] = node
[Link] = node
else:
[Link] = node
[Link] = node
[Link] += 1

def delete_item(self, data):

# Delete an item from the list
current = [Link]
prev = [Link]
while current:
if [Link] == data:
if current == [Link]:
23 | P a g e
 [Link] = [Link]
else:
[Link] = [Link]
[Link] -= 1
return
prev = current
current = [Link]
def iterate_item(self):
# Iterate the list.
current_item = [Link]
while current_item:
val = current_item.data
current_item = current_item.next
yield val

items = singly_linked_list()
items.append_item('PHP')
items.append_item('Python')
items.append_item('C#')
items.append_item('C++')
items.append_item('Java')

print("Original list:")
for val in items.iterate_item():
print(val)

print("\nAfter removing the first item from the list:")

24 | P a g e
items.delete_item('PHP')
for val in items.iterate_item():
print(val)
Output:-

Ques16. Write a Python program to create circular single linked

lists.
Ans.
#Represents the node of list.
class Node:
def __init__(self,data):
[Link] = data
[Link] = None

25 | P a g e
class CreateList:
#Declaring head and tail pointer as null.
def __init__(self):
[Link] = Node(None)
[Link] = Node(None)
[Link] = [Link]
[Link] = [Link]

#This function will add the new node at the end of the list.
def add(self,data):
newNode = Node(data)
#Checks if the list is empty.
if [Link] is None:
#If list is empty, both head and tail would point to new node.
[Link] = newNode
[Link] = newNode
[Link] = [Link]
else:
#tail will point to new node.
[Link] = newNode
#New node will become new tail.
[Link] = newNode
#Since, it is circular linked list tail will point to head.
[Link] = [Link]

#Displays all the nodes in the list

def display(self):
current = [Link]
if [Link] is None:
print("List is empty")
return
else:
print("Nodes of the circular linked list: ")
#Prints each node by incrementing pointer.
print([Link]),
while([Link] != [Link]):
current = [Link]
print([Link])

class CircularLinkedList:
cl = CreateList()
#Adds data to the list
[Link](1)

26 | P a g e
 [Link](2)
[Link](3)
[Link](4)
#Displays all the nodes present in the list
[Link]()
Output:-

Ques17. Write Python programs to implement stack and its

operations using list.
Ans.
stack = []
# append() function to push element in the stack
[Link]('a')
[Link]('b')

27 | P a g e
[Link]('c')
print('Initial stack')
print(stack)
# pop() function to push element in stack
print('\nElements pushed in stack:')
[Link]('e')
[Link]('f')
[Link]('g')
print('\nStack after elements are pushed:')
print(stack)
# pop() function to pop element from stack in LIFO order
print('\nElements popped from stack:')
print([Link]())
print([Link]())
print([Link]())
print('\nStack after elements are popped:')
print(stack)

Output:-

28 | P a g e
Ques18. Write Python programs to implement queue and its
operations using list.
Ans.
29 | P a g e
# Initializing a queue
queue = []
# Adding elements to the queue
[Link]('a')
[Link]('b')
[Link]('c')
print("Initial queue")
print(queue)
# Removing elements from the queue
print("\nElements dequeued from queue")
print([Link](0))
print([Link](0))
print([Link](0))
print("\nQueue after removing elements")
print(queue)
# Uncommenting print([Link](0)) will raise and IndexError as the
queue is now empty
Output:-

Ques19. Write a Python program to create a Balanced Binary

Search Tree (BST) using an array (given) elements where array
elements are sorted in ascending order.
Ans.

30 | P a g e
# binary tree node
class Node:
def __init__(self, d):
[Link] = d
[Link] = None
[Link] = None

# function to convert sorted array to a balanced BST

# input : sorted array of integers
# output: root node of balanced BST
def sortedArrayToBST(arr):
if not arr:
return None
# find middle index
mid = (len(arr)) // 2
# make the middle element the root
root = Node(arr[mid])
# left subtree of root has all values <arr[mid]
[Link] = sortedArrayToBST(arr[:mid])
# right subtree of root has all values >arr[mid]
[Link] = sortedArrayToBST(arr[mid+1:])
return root

# A utility function to print the preorder traversal of the BST

def preOrder(node):
if not node:
return

31 | P a g e
 print([Link])
preOrder([Link])
preOrder([Link])

arr = [1, 2, 3, 4, 5, 6, 7]
root = sortedArrayToBST(arr)
print("PreOrder Traversal of constructed BST ")
preOrder(root)
Output:-

2 6

1 3 5 7

Ques20. Write a Python program to find the kth smallest element in

a given a binary search tree.
Ans.
# A BST node
class Node:

32 | P a g e
 def __init__(self, key):
[Link] = key
[Link] = None
[Link] = None
# Recursive function to insert an key into BST
def insert(root, x):
if (root == None):
return Node(x)
if (x < [Link]):
[Link] = insert([Link], x)
elif (x > [Link]):
[Link] = insert([Link], x)
return root
# Function to find k'th largest element in BST. Here count denotes the
number of nodes processed so far
def kthSmallest(root):
global k
# Base case
if (root == None):
return None
# Search in left subtree
left = kthSmallest([Link])
# If k'th smallest is found in left subtree, return it
if (left != None):
return left
# If current element is k'th smallest, return it
k -= 1
if (k == 0):

33 | P a g e
 return root
# Else search in right subtree
return kthSmallest([Link])
# Function to find k'th largest element in BST
def printKthSmallest(root):
res = kthSmallest(root)
if (res == None):
print("There are less than k nodes in the BST")
else:
print("K-th Smallest Element is ", [Link])
# Driver code
if __name__ == '__main__':
root = None
keys = [20, 8, 22, 4, 12, 10, 14]
for x in keys:
root = insert(root, x)
k=3
printKthSmallest(root)
Output:-

Ques21. Write a Python program to traverse the binary tree using

pre-order, post-order and in-order traversals.
Ans.
# A class that represents an individual node in a Binary Tree
class Node:
def __init__(self, key):
[Link] = None
34 | P a g e
 [Link] = None
[Link] = key
# A function to do inorder tree traversal
def printInorder(root):
if root:
# First recur on left child
printInorder([Link])
# then print the data of node
print([Link]),
# now recur on right child
printInorder([Link])
# A function to do preorder tree traversal
def printPreorder(root):
if root:
# First print the data of node
print([Link]),
# Then recur on left child
printPreorder([Link])
# Finally recur on right child
printPreorder([Link])
# A function to do postorder tree traversal
def printPostorder(root):
if root:
# First recur on left child
printPostorder([Link])
# the recur on right child
printPostorder([Link])

35 | P a g e
 # now print the data of node
print([Link])
# Driver code
if __name__ == "__main__":
root = Node(1)
[Link] = Node(2)
[Link] = Node(3)
[Link] = Node(4)
[Link] = Node(5)
# Function call
print("\nInorder traversal of binary tree is")
printInorder(root)
print("Preorder traversal of binary tree is")
printPreorder(root)
print("\nPostorder traversal of binary tree is")
printPostorder(root)

Output:-

36 | P a g e
Ques22. Write a Python program to count the number of nodes in
binary search tree.

37 | P a g e
Ans.
# Structure of a Tree Node
class node:
def __init__(self, key):
[Link] = None
[Link] = None
[Link] = key
# Function to get the left height of the binary tree
def left_height(node):
ht = 0
while(node):
ht += 1
node = [Link]
# Return the left height obtained
return ht
# Function to get the right height of the binary tree
def right_height(node):
ht = 0
while(node):
ht += 1
node = [Link]
# Return the right height obtained
return ht
# Function to get the count of nodes in complete binary tree
def TotalNodes(root):
# Base case
if(root == None):
return 0
# Find the left height and the right heights
lh = left_height(root)
rh = right_height(root)
# If left and right heights are equal return 2^height(1<<height) -1
if(lh == rh):
return (1 << lh) - 1
# Otherwise, recursive call
return 1 + TotalNodes([Link]) + TotalNodes([Link])
# Driver code
root = node(1)
[Link] = node(2)
[Link] = node(3)
[Link] = node(4)
[Link] = node(5)
[Link] = node(9)

38 | P a g e
[Link] = node(8)
[Link] = node(6)
[Link] = node(7)
print("Total nodes are:",TotalNodes(root))

Output:-

Ques23. Write a Python program to traverse the graph using Depth

First Search and Breadth First Search.
Ans.

39 | P a g e
# Python program to print DFS traversal for complete graph

from collections import defaultdict

# This class represents a directed graph using adjacency list
representation
class Graph:
# Constructor
def __init__(self):
# default dictionary to store graph
[Link] = defaultdict(list)
# function to add an edge to graph
def addEdge(self,u,v):
[Link][u].append(v)
# A function used by DFS
def DFSUtil(self, v, visited):
# Mark the current node as visited and print it
visited[v]= True
print(v)
# Recur for all the vertices adjacent to this vertex
for i in [Link][v]:
if visited[i] == False:
[Link](i, visited)

40 | P a g e
 # The function to do DFS traversal. It uses recursive DFSUtil()
def DFS(self):
V = len([Link]) #total vertices
# Mark all the vertices as not visited
visited =[False]*(V)
# Call the recursive helper function to print DFS traversal
starting from all vertices one by one
for i in range(V):
if visited[i] == False:
[Link](i, visited)
# Driver code
# Create a graph given in the above diagram
g = Graph()
[Link](0, 1)
[Link](0, 2)
[Link](1, 2)
[Link](2, 0)
[Link](2, 3)
[Link](3, 3)
print("Following is Depth First Traversal")
[Link]()
Output:-

# Python3 Program to print BFS traversal from a given source vertex.

BFS(int s) traverses vertices reachable from s.

41 | P a g e
from collections import defaultdict
# This class represents a directed graph using adjacency list
representation
class Graph:
# Constructor
def __init__(self):
# default dictionary to store graph
[Link] = defaultdict(list)
# function to add an edge to graph
def addEdge(self,u,v):
[Link][u].append(v)
# Function to print a BFS of graph
def BFS(self, s):
# Mark all the vertices as not visited
visited = [False] * (len([Link]))
# Create a queue for BFS
queue = []
# Mark the source node as visited and enqueue it
[Link](s)
visited[s] = True
while queue:
# Dequeue a vertex from

42 | P a g e
 # queue and print it
s = [Link](0)
print (s, end = " ")
# Get all adjacent vertices of the dequeued vertex s.
# If a adjacent has not been visited,
# then mark it visited and enqueue it
for i in [Link][s]:
if visited[i] == False:
[Link](i)
visited[i] = True
# Driver code
# Create a graph given in the above diagram
g = Graph()
[Link](0, 1)
[Link](0, 2)
[Link](1, 2)
[Link](2, 0)
[Link](2, 3)
[Link](3, 3)
print ("Following is Breadth First Traversal"
" (starting from vertex 2)")
[Link](2)
Output:-

Ques24. Write a Python program to create Red Black Tree and

perform operations of Insertion and Deletion in it.
Ans.

43 | P a g e
import sys
# Node creation
class Node():
def __init__(self, item):
[Link] = item
[Link] = None
[Link] = None
[Link] = None
[Link] = 1
class RedBlackTree():
def __init__(self):
[Link] = Node(0)
[Link] = 0
[Link] = None
[Link] = None
[Link] = [Link]
# Preorder
def pre_order_helper(self, node):
if node != [Link]:
[Link]([Link] + " ")
self.pre_order_helper([Link])
self.pre_order_helper([Link])
# Inorder
def in_order_helper(self, node):
if node != [Link]:
self.in_order_helper([Link])
[Link]([Link] + " ")

44 | P a g e
 self.in_order_helper([Link])
# Postorder
def post_order_helper(self, node):
if node != [Link]:
self.post_order_helper([Link])
self.post_order_helper([Link])
[Link]([Link] + " ")
# Search the tree
def search_tree_helper(self, node, key):
if node == [Link] or key == [Link]:
return node
if key < [Link]:
return self.search_tree_helper([Link], key)
return self.search_tree_helper([Link], key)
# Balancing the tree after deletion
def delete_fix(self, x):
while x != [Link] and [Link] == 0:
if x == [Link]:
s = [Link]
if [Link] == 1:
[Link] = 0
[Link] = 1
self.left_rotate([Link])
s = [Link]
if [Link] == 0 and [Link] == 0:
[Link] = 1
x = [Link]

45 | P a g e
 else:
if [Link] == 0:
[Link] = 0
[Link] = 1
self.right_rotate(s)
s = [Link]
[Link] = [Link]
[Link] = 0
[Link] = 0
self.left_rotate([Link])
x = [Link]
else:
s = [Link]
if [Link] == 1:
[Link] = 0
[Link] = 1
self.right_rotate([Link])
s = [Link]
if [Link] == 0 and [Link] == 0:
[Link] = 1
x = [Link]
else:
if [Link] == 0:
[Link] = 0
[Link] = 1
self.left_rotate(s)
s = [Link]

46 | P a g e
 [Link] = [Link]
[Link] = 0
[Link] = 0
self.right_rotate([Link])
x = [Link]
[Link] = 0
def __rb_transplant(self, u, v):
if [Link] == None:
[Link] = v
elif u == [Link]:
[Link] = v
else:
[Link] = v
[Link] = [Link]
# Node deletion
def delete_node_helper(self, node, key):
z = [Link]
while node != [Link]:
if [Link] == key:
z = node
if [Link] <= key:
node = [Link]
else:
node = [Link]
if z == [Link]:
print("Cannot find key in the tree")
return

47 | P a g e
 y=z
y_original_color = [Link]
if [Link] == [Link]:
x = [Link]
self.__rb_transplant(z, [Link])
elif ([Link] == [Link]):
x = [Link]
self.__rb_transplant(z, [Link])
else:
y = [Link]([Link])
y_original_color = [Link]
x = [Link]
if [Link] == z:
[Link] = y
else:
self.__rb_transplant(y, [Link])
[Link] = [Link]
[Link] = y
self.__rb_transplant(z, y)
[Link] = [Link]
[Link] = y
[Link] = [Link]
if y_original_color == 0:
self.delete_fix(x)
# Balance the tree after insertion
def fix_insert(self, k):
while [Link] == 1:

48 | P a g e
if [Link] == [Link]:
u = [Link]
if [Link] == 1:
[Link] = 0
[Link] = 0
[Link] = 1
k = [Link]
else:
if k == [Link]:
k = [Link]
self.right_rotate(k)
[Link] = 0
[Link] = 1
self.left_rotate([Link])
else:
u = [Link]
if [Link] == 1:
[Link] = 0
[Link] = 0
[Link] = 1
k = [Link]
else:
if k == [Link]:
k = [Link]
self.left_rotate(k)
[Link] = 0
[Link] = 1

49 | P a g e
 self.right_rotate([Link])
if k == [Link]:
break
[Link] = 0
# Printing the tree
def __print_helper(self, node, indent, last):
if node != [Link]:
[Link](indent)
if last:
[Link]("R----")
indent += " "
else:
[Link]("L----")
indent += "| "
s_color = "RED" if [Link] == 1 else "BLACK"
print(str([Link]) + "(" + s_color + ")")
self.__print_helper([Link], indent, False)
self.__print_helper([Link], indent, True)
def preorder(self):
self.pre_order_helper([Link])
def inorder(self):
self.in_order_helper([Link])
def postorder(self):
self.post_order_helper([Link])
def searchTree(self, k):
return self.search_tree_helper([Link], k)
def minimum(self, node):

50 | P a g e
 while [Link] != [Link]:
node = [Link]
return node
def maximum(self, node):
while [Link] != [Link]:
node = [Link]
return node
def successor(self, x):
if [Link] != [Link]:
return [Link]([Link])
y = [Link]
while y != [Link] and x == [Link]:
x=y
y = [Link]
return y
def predecessor(self, x):
if ([Link] != [Link]):
return [Link]([Link])
y = [Link]
while y != [Link] and x == [Link]:
x=y
y = [Link]
return y
def left_rotate(self, x):
y = [Link]
[Link] = [Link]
if [Link] != [Link]:

51 | P a g e
 [Link] = x
[Link] = [Link]
if [Link] == None:
[Link] = y
elif x == [Link]:
[Link] = y
else:
[Link] = y
[Link] = x
[Link] = y
def right_rotate(self, x):
y = [Link]
[Link] = [Link]
if [Link] != [Link]:
[Link] = x
[Link] = [Link]
if [Link] == None:
[Link] = y
elif x == [Link]:
[Link] = y
else:
[Link] = y
[Link] = x
[Link] = y
def insert(self, key):
node = Node(key)
[Link] = None

52 | P a g e
 [Link] = key
[Link] = [Link]
[Link] = [Link]
[Link] = 1
y = None
x = [Link]
while x != [Link]:
y=x
if [Link] < [Link]:
x = [Link]
else:
x = [Link]
[Link] = y
if y == None:
[Link] = node
elif [Link] < [Link]:
[Link] = node
else:
[Link] = node
if [Link] == None:
[Link] = 0
return
if [Link] == None:
return
self.fix_insert(node)
def get_root(self):
return [Link]

53 | P a g e
 def delete_node(self, item):
self.delete_node_helper([Link], item)
def print_tree(self):
self.__print_helper([Link], "", True)
if __name__ == "__main__":
bst = RedBlackTree()
[Link](55)
[Link](40)
[Link](65)
[Link](60)
[Link](75)
[Link](57)
print("\nAfter inserting an elements")
bst.print_tree()
print("\nAfter deleting an element")
bst.delete_node(40)
bst.print_tree()

Output:-

54 | P a g e
Ques25. Write a Python program to implement AVL Trees as well as
various operations of searching, insertion and deletion on AVL
Trees.
Ans.

55 | P a g e
import sys
# Create a tree node
class TreeNode(object):
def __init__(self, key):
[Link] = key
[Link] = None
[Link] = None
[Link] = 1
class AVLTree(object):
# Function to insert a node
def insert_node(self, root, key):
# Find the correct location and insert the node
if not root:
return TreeNode(key)
elif key < [Link]:
[Link] = self.insert_node([Link], key)
else:
[Link] = self.insert_node([Link], key)
[Link] = 1 + max([Link]([Link]),
[Link]([Link]))
# Update the balance factor and balance the tree
balanceFactor = [Link](root)
if balanceFactor > 1:
if key < [Link]:
return [Link](root)
else:
[Link] = [Link]([Link])

56 | P a g e
 return [Link](root)
if balanceFactor < -1:
if key > [Link]:
return [Link](root)
else:
[Link] = [Link]([Link])
return [Link](root)
return root
# Function to delete a node
def delete_node(self, root, key):
# Find the node to be deleted and remove it
if not root:
return root
elif key < [Link]:
[Link] = self.delete_node([Link], key)
elif key > [Link]:
[Link] = self.delete_node([Link], key)
else:
if [Link] is None:
temp = [Link]
root = None
return temp
elif [Link] is None:
temp = [Link]
root = None
return temp
temp = [Link]([Link])

57 | P a g e
 [Link] = [Link]
[Link] = self.delete_node([Link],
[Link])
if root is None:
return root
# Update the balance factor of nodes
[Link] = 1 + max([Link]([Link]),
[Link]([Link]))

balanceFactor = [Link](root)
# Balance the tree
if balanceFactor > 1:
if [Link]([Link]) >= 0:
return [Link](root)
else:
[Link] = [Link]([Link])
return [Link](root)
if balanceFactor < -1:
if [Link]([Link]) <= 0:
return [Link](root)
else:
[Link] = [Link]([Link])
return [Link](root)
return root
# Function to perform left rotation
def leftRotate(self, z):
y = [Link]

58 | P a g e
 T2 = [Link]
[Link] = z
[Link] = T2
[Link] = 1 + max([Link]([Link]),
[Link]([Link]))
[Link] = 1 + max([Link]([Link]),
[Link]([Link]))
return y
# Function to perform right rotation
def rightRotate(self, z):
y = [Link]
T3 = [Link]
[Link] = z
[Link] = T3
[Link] = 1 + max([Link]([Link]),
[Link]([Link]))
[Link] = 1 + max([Link]([Link]),
[Link]([Link]))
return y
# Get the height of the node
def getHeight(self, root):
if not root:
return 0
return [Link]
# Get balance factore of the node
def getBalance(self, root):
if not root:

59 | P a g e
 return 0
return [Link]([Link]) - [Link]([Link])
def getMinValueNode(self, root):
if root is None or [Link] is None:
return root
return [Link]([Link])
def preOrder(self, root):
if not root:
return
print("{0} ".format([Link]), end="")
[Link]([Link])
[Link]([Link])
# Print the tree
def printHelper(self, currPtr, indent, last):
if currPtr != None:
[Link](indent)
if last:
[Link]("R----")
indent += " "
else:
[Link]("L----")
indent += "| "
print([Link])
[Link]([Link], indent, False)
[Link]([Link], indent, True)
myTree = AVLTree()
root = None

60 | P a g e
nums = [33, 13, 52, 9, 21, 61, 8, 11]
for num in nums:
root = myTree.insert_node(root, num)
print("After Insertion: ")
[Link](root, "", True)
key = 13
root = myTree.delete_node(root, key)
print("After Deletion: ")
[Link](root, "", True)
Output:-

61 | P a g e