About
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
Selection Sort
Bubble Sort
Insertion Sort
Merge sort 1
Merge Sort 2
Quick sort 1
Quick Sort 2
Singly Linked List SLL
Doubly linked list DLL
Circular Linked list CLL
Linked Stack
Stack
Queue
Queue Linked List
Deque
Circular Queue
Binary tree and traversals
binary tree using list
binary search tree
Priority queue
Min heap
Max Heap
Hash table:
Graph
Weighted graph
Selection Sort
def selection_sort(arr): n = len(arr) for i in range(n-1): min_index = i for j in range(i+1, n): if arr[j] < arr[min_index]: min_index = j arr[i], arr[min_index] = arr[min_index], arr[i] return arr
Bubble Sort
def bubble_sort(arr): n = len(arr) for i in range(n-1): for j in range(n-1-i): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr
Insertion Sort
def insertion_sort(arr): n = len(arr) for i in range(1, n): key = arr[i] j = i - 1 while j >= 0 and arr[j] > key: arr[j+1] = arr[j] j -= 1 arr[j+1] = key return arr
Merge sort 1
def merge_sort(arr): if len(arr) <= 1: return arr
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
left_half = merge_sort(left_half)
right_half = merge_sort(right_half)
return merge(left_half, right_half)def merge(left, right): merged = [] left_index, right_index = 0, 0
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
merged.append(left[left_index])
left_index += 1
else:
merged.append(right[right_index])
right_index += 1
while left_index < len(left):
merged.append(left[left_index])
left_index += 1
while right_index < len(right):
merged.append(right[right_index])
right_index += 1
return mergedarr = [9, 3, 6, 2, 8, 1, 5, 4, 7] sorted_arr = merge_sort(arr) print(sorted_arr)
Merge Sort 2
def mergesort(a, lb, ub): if lb < ub: mid = (lb + ub) // 2 mergesort(a, lb, mid) mergesort(a, mid + 1, ub) merge(a, lb, mid, ub) def merge(a, lb, mid, ub): i = lb j = mid + 1 k = lb temp = [None] * len(a) while i <= mid and j <= ub: if a[i] <= a[j]: temp[k] = a[i] i += 1 k += 1 else: temp[k] = a[j] j += 1 k += 1 while j <= ub: temp[k] = a[j] j += 1 k += 1 while i <= mid: temp[k] = a[i] i += 1 k += 1 for k in range(lb,ub+1): a[k] = temp[k]
A = [7,6,10,5,9,2,1,15] ub = len(A) lb = 0 mergesort(A, lb, ub-1) print(A)
Quick sort 1
def partition (a, start, end):
i = (start - 1)
pivot = a[end]
for j in range(start, end):
if (a[j] <= pivot):
i = i + 1
a[i], a[j] = a[j], a[i]
a[i+1], a[end] = a[end], a[i+1]
return (i + 1)def quick(a, start, end):
if (start < end):
p = partition(a, start, end)
quick(a, start, p - 1)
quick(a, p + 1, end)
def printArr(a):
for i in range(len(a)):
print (a[i], end = " ")
a = [68, 13, 1, 49, 58]
print("Before sorting array elements are - ")
printArr(a)
quick(a, 0, len(a)-1)
print("\nAfter sorting array elements are - ")
printArr(a)
Quick Sort 2
def quick_sort(arr): if len(arr) <= 1: return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)arr = [9, 3, 6, 2, 8, 1, 5, 4, 7] sorted_arr = quick_sort(arr) print(sorted_arr)
Singly Linked List SLL
class Node: def __init__(self,value): self.next = None self.value = value
class SLL: def __init__(self): self.head = None self.tail = None
def insert(self,value,location):
node = Node(value)
if self.head is None:
self.head = node
self.tail = node
else:
if location == 0:
node.next = self.head
self.head = node
elif location == -1:
self.tail.next = node
self.tail = node
else:
tempNode = self.head
index = 0
while index<location -1:
index+=1
tempNode = tempNode.next
node.next = tempNode.next
tempNode.next = node
if tempNode == self.tail:
self.tail = node
def delete(self,location):
if self.head is None:
print("SLL doesn't exist")
elif self.head == self.tail:
self.head = None
self.tail = None
else:
if location == 0:
self.head = self.head.next
elif location == -1:
tempNode = self.head
while tempNode:
if tempNode.next == self.tail:
break
tempNode = tempNode.next
tempNode.next = None
self.tail = tempNode
else:
tempNode = self.head
index = 0
while index < location -1:
index+=1
tempNode = tempNode.next
tempNode.next = tempNode.next.nextDoubly linked list DLL
class Node: def __init__(self, value=None): self.value = value self.next = None self.prev = None class DLL: def __init__(self): self.head = None self.tail = None def __iter__(self): node = self.head while node: yield node node = node.next def insertDLL(self, value, location): if self.head is None: newNode = Node(value) self.head = newNode self.tail = newNode else: newNode = Node(value) if location == 0: newNode.prev = None newNode.next = self.head self.head.prev = newNode self.head = newNode elif location == -1: newNode.next = None newNode.prev = self.tail self.tail.next = newNode self.tail = newNode else: tempNode = self.head index = 0 while index < location - 1: tempNode = self.head index += 1 if tempNode == self.tail: newNode.prev = self.tail self.tail.next = newNode self.tail = newNode else: newNode.next = tempNode.next newNode.prev = tempNode tempNode.next.prev = newNode tempNode.next = newNode
def traversalDLL(self):
if self.head is None:
print("The DLL has no element present in it")
else:
tempNode = self.head
while tempNode:
print(tempNode.value)
tempNode = tempNode.next
def reversetraversalDLL(self):
if self.head is None:
print("The DLL has no element present in it")
else:
tempNode = self.tail
while tempNode:
print(tempNode.value)
tempNode = tempNode.prev
def searchDLL(self, value):
if self.head is None:
print("The DLL has no element present in it")
else:
tempNode = self.head
while tempNode:
if tempNode.value == value:
print(tempNode.value)
tempNode = tempNode.next
return "The element is not present in this DLL"
def deletenode(self, location):
if self.head is None:
print("The DLL has no elements present in it")
else:
if location == 0:
if self.head == self.tail:
self.head = None
self.tail = None
else:
self.head = self.head.next
self.head.prev = None
elif location == -1:
if self.head == self.tail:
self.head = None
self.tail = None
else:
self.tail = self.tail.prev
self.tail.next = None
else:
tempNode = self.head
index = 0
while index < location - 1:
tempNode = tempNode.next
index += 1
tempNode.next = tempNode.next.next
tempNode.next.prev = tempNode
print("The node has been deleted")
def deleteDLL(self):
if self.head is None:
print("The DLL has no elements present in it")
else:
tempNode = self.head
while tempNode:
tempNode.prev = None
tempNode = tempNode.next
self.head = None
self.tail = None
print("The DLL has been successfully deleted")doubly = DLL() doubly.createDLL(2) doubly.insertDLL(3, 1) doubly.insertDLL(4, 1) doubly.insertDLL(1, 8) print([node.value for node in doubly]) doubly.traversalDLL() doubly.createDLL(10) doubly.insertDLL(5, 1) doubly.insertDLL(6, 1) doubly.insertDLL(7, 2) print([node.value for node in doubly])
Circular Linked list CLL
class Node: def __init__(self, value=None): self.value = value self.next = None
class CSLL:
def __init__(self):
self.tail = None
self.head = None
def __iter__(self):
node = self.head
while node is not None:
yield node
node = node.next
if node == self.tail.next:
break
def createCSLL(self, nodevalue):
node = Node(nodevalue)
node.next = node
self.head = node
self.tail = node
return "The CSLL has been created"
def insertCSLL(self, value, location):
if self.head is None:
print("CSLL doesn't exist")
else:
newNode = Node(value)
if location == 0:
newNode.next = self.head
self.head = newNode
self.tail.next = newNode
elif location == -1:
newNode.next = self.tail.next
self.tail.next = newNode
self.tail = newNode
else:
tempNode = self.head
index = 0
while index < location - 1:
tempNode = tempNode.next
index += 1
nextNode = tempNode.next
tempNode.next = newNode
newNode.next = nextNode
return "The specified value has been inserted"
def traversalCSLL(self):
if self.head is None:
print("CSLL doesn't exist")
else:
tempNode = self.head
while tempNode:
print(tempNode.value)
tempNode = tempNode.next
if tempNode == self.tail.next:
break
def searchCSLL(self, value):
if self.head is None:
print("CSLL doesn't exist")
else:
tempNode = self.head
while tempNode:
if tempNode.value == value:
return tempNode.value
tempNode = tempNode.next
if tempNode == self.tail.next:
return "The value doesn't exist"
def deletenode(self, location):
if self.head is None:
print("CSLL doesn't exist")
else:
if location == 0:
if self.head == self.tail:
self.head = None
self.tail = None
self.head.next = None
else:
self.head = self.head.next
self.tail.next = self.head
elif location == 1:
if self.head == self.tail:
self.head = None
self.tail = None
self.head.next = None
else:
node = self.head
while node is not None:
if node.next == self.tail:
break
node = node.next
node.next = self.head
self.tail = node
else:
tempNode = self.head
index = 0
while index < location - 1:
tempNode = tempNode.next
index += 1
nextNode = tempNode.next
tempNode.next = nextNode.next
def deleteEntireCSLL(self):
self.head = None
self.tail.next = None
self.tail = NonecircularSLL = CSLL() circularSLL.createCSLL(0) circularSLL.insertCSLL(1, 1) circularSLL.insertCSLL(2, 1) circularSLL.insertCSLL(4, 2) circularSLL.insertCSLL(3, 1)
print([node.value for node in circularSLL])
Linked Stack
class Node: def __init__(self, data): self.data = data self.next = None
class Stack:
def __init__(self):
self.head = None
def isempty(self):
if self.head == None:
return True
else:
return False
def push(self, data):
if self.head == None:
self.head = Node(data)
else:
newnode = Node(data)
newnode.next = self.head
self.head = newnode
def pop(self):
if self.isempty():
return None
else:
poppednode = self.head
self.head = self.head.next
poppednode.next = None
return poppednode.data
def peek(self):
if self.isempty():
return None
else:
return self.head.data
def display(self):
iternode = self.head
if self.isempty():
print("Stack Underflow")
else:
while(iternode != None):
print(iternode.data, end = "")
iternode = iternode.next
if(iternode != None):
print(" -> ", end = "")
returnStack
class ListBasedStack: def __init__(self): self.stack = []
def is_empty(self):
return len(self.stack) == 0
def push(self, data):
self.stack.append(data)
def pop(self):
if self.is_empty():
raise IndexError("Stack is empty.")
return self.stack.pop()
def peek(self):
if self.is_empty():
raise IndexError("Stack is empty.")
return self.stack[-1]
def size(self):
return len(self.stack)Queue
class ListBasedQueue: def __init__(self): self.queue = []
def is_empty(self):
return len(self.queue) == 0
def enqueue(self, item):
self.queue.append(item)
def dequeue(self):
if self.is_empty():
raise IndexError("Queue is empty.")
return self.queue.pop(0)
def peek(self):
if self.is_empty():
raise IndexError("Queue is empty.")
return self.queue[0]
def size(self):
return len(self.queue)Queue Linked List
class Node: def __init__(self, data): self.data = data self.next = None
class LinkedListQueue: def __init__(self): self.front = None self.rear = None
def is_empty(self):
return self.front is None
def enqueue(self, data):
new_node = Node(data)
if self.is_empty():
self.front = new_node
self.rear = new_node
else:
self.rear.next = new_node
self.rear = new_node
def dequeue(self):
if self.is_empty():
raise IndexError("Queue is empty.")
data = self.front.data
self.front = self.front.next
if self.front is None:
self.rear = None
return data
def peek(self):
if self.is_empty():
raise IndexError("Queue is empty.")
return self.front.data
def size(self):
count = 0
current = self.front
while current is not None:
count += 1
current = current.next
return countDeque
class Deque: def __init__(self): self.deque = []
def is_empty(self):
return len(self.deque) == 0
def insert_front(self, data):
self.deque.insert(0, data)
def insert_rear(self, data):
self.deque.append(data)
def delete_front(self):
if self.is_empty():
raise IndexError("Deque is empty.")
return self.deque.pop(0)
def delete_rear(self):
if self.is_empty():
raise IndexError("Deque is empty.")
return self.deque.pop()
def get_front(self):
if self.is_empty():
raise IndexError("Deque is empty.")
return self.deque[0]
def get_rear(self):
if self.is_empty():
raise IndexError("Deque is empty.")
return self.deque[-1]
def size(self):
return len(self.deque)Circular Queue
class CircularQueue: def __init__(self, capacity): self.capacity = capacity self.queue = [None] * capacity self.front = -1 self.rear = -1
def is_empty(self):
return self.front == -1
def is_full(self):
return (self.rear + 1) % self.capacity == self.front
def enqueue(self, item):
if self.is_full():
raise IndexError("Queue is full.")
if self.is_empty():
self.front = 0
self.rear = (self.rear + 1) % self.capacity
self.queue[self.rear] = item
def dequeue(self):
if self.is_empty():
raise IndexError("Queue is empty.")
item = self.queue[self.front]
if self.front == self.rear:
self.front = -1
self.rear = -1
else:
self.front = (self.front + 1) % self.capacity
return item
def get_front(self):
if self.is_empty():
raise IndexError("Queue is empty.")
return self.queue[self.front]
def get_rear(self):
if self.is_empty():
raise IndexError("Queue is empty.")
return self.queue[self.rear]Binary tree and traversals
class TreeNode: def __init__(self, data): self.data = data self.left = None self.right = None
class BinaryTree: def __init__(self): self.root = None
def insert(self, data):
if self.root is None:
self.root = TreeNode(data)
else:
self._insert_recursive(data, self.root)
def _insert_recursive(self, data, node):
if data < node.data:
if node.left is None:
node.left = TreeNode(data)
else:
self._insert_recursive(data, node.left)
else:
if node.right is None:
node.right = TreeNode(data)
else:
self._insert_recursive(data, node.right)
def inorder_traversal(self):
self._inorder_recursive(self.root)
def _inorder_recursive(self, node):
if node:
self._inorder_recursive(node.left)
print(node.data, end=" ")
self._inorder_recursive(node.right)
def preorder_traversal(self):
self._preorder_recursive(self.root)
def _preorder_recursive(self, node):
if node:
print(node.data, end=" ")
self._preorder_recursive(node.left)
self._preorder_recursive(node.right)
def postorder_traversal(self):
self._postorder_recursive(self.root)
def _postorder_recursive(self, node):
if node:
self._postorder_recursive(node.left)
self._postorder_recursive(node.right)
print(node.data, end=" ")binary tree using list
class BinaryTree: def __init__(self): self.tree = []
def insert(self, data):
self.tree.append(data)
def inorder_traversal(self, index=0):
if index < len(self.tree):
self.inorder_traversal(2 * index + 1)
print(self.tree[index], end=" ")
self.inorder_traversal(2 * index + 2)
def preorder_traversal(self, index=0):
if index < len(self.tree):
print(self.tree[index], end=" ")
self.preorder_traversal(2 * index + 1)
self.preorder_traversal(2 * index + 2)
def postorder_traversal(self, index=0):
if index < len(self.tree):
self.postorder_traversal(2 * index + 1)
self.postorder_traversal(2 * index + 2)
print(self.tree[index], end=" ")
def print_tree(self):
print(self.tree)binary search tree
class TreeNode: def __init__(self, data): self.data = data self.left = None self.right = None
class BinarySearchTree: def __init__(self): self.root = None
def insert(self, data):
if self.root is None:
self.root = TreeNode(data)
else:
self._insert_recursive(data, self.root)
def _insert_recursive(self, data, node):
if data < node.data:
if node.left is None:
node.left = TreeNode(data)
else:
self._insert_recursive(data, node.left)
else:
if node.right is None:
node.right = TreeNode(data)
else:
self._insert_recursive(data, node.right)
def inorder_traversal(self):
self._inorder_recursive(self.root)
def _inorder_recursive(self, node):
if node:
self._inorder_recursive(node.left)
print(node.data, end=" ")
self._inorder_recursive(node.right)
def preorder_traversal(self):
self._preorder_recursive(self.root)
def _preorder_recursive(self, node):
if node:
print(node.data, end=" ")
self._preorder_recursive(node.left)
self._preorder_recursive(node.right)
def postorder_traversal(self):
self._postorder_recursive(self.root)
def _postorder_recursive(self, node):
if node:
self._postorder_recursive(node.left)
self._postorder_recursive(node.right)
print(node.data, end=" ")
def level_order_traversal(self):
if self.root is None:
return
queue = [self.root]
while queue:
node = queue.pop(0)
print(node.data, end=" ")
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
def subtree_height(self, node):
if node is None:
return -1
else:
left_height = self.subtree_height(node.left)
right_height = self.subtree_height(node.right)
return max(left_height, right_height) + 1
def tree_height(self):
return self.subtree_height(self.root)
def print_nodes_at_level(self, level):
self._print_nodes_at_level(self.root, level)
def _print_nodes_at_level(self, node, level):
if node is None:
return
if level == 0:
print(node.data, end=" ")
else:
self._print_nodes_at_level(node.left, level - 1)
self._print_nodes_at_level(node.right, level - 1)
def print_leaf_nodes(self):
self._print_leaf_nodes(self.root)
def _print_leaf_nodes(self, node):
if node is None:
return
if node.left is None and node.right is None:
print(node.data, end=" ")
self._print_leaf_nodes(node.left)
self._print_leaf_nodes(node.right)
def print_non_leaf_nodes(self):
self._print_non_leaf_nodes(self.root)
def _print_non_leaf_nodes(self, node):
if node is None or (node.left is None and node.right is None):
return
print(node.data, end=" ")
self._print_non_leaf_nodes(node.left)
self._print_non_leaf_nodes(node.right)
def right_view(self):
self._right_view(self.root, 1, [0])
def _right_view(self, node, current_level, max_level):
if node is None:
return
if current_level > max_level[0]:
print(node.data, end=" ")
max_level[0] = current_level
self._right_view(node.right, current_level + 1, max_level)
self._right_view(node.left, current_level + 1, max_level)
def left_view(self):
self._left_view(self.root, 1, [0])
def _left_view(self, node, current_level, max_level):
if node is None:
return
if current_level > max_level[0]:
print(node.data, end=" ")
max_level[0] = current_level
self._left_view(node.left, current_level + 1, max_level)
self._left_view(node.right, current_level + 1, max_level)
def delete_node(self, key):
self.root = self._delete_node_recursive(self.root, key)
def _delete_node_recursive(self, node, key):
if node is None:
return node
if key < node.data:
node.left = self._delete_node_recursive(node.left, key)
elif key > node.data:
node.right = self._delete_node_recursive(node.right, key)
else:
if node.left is None:
return node.right
elif node.right is None:
return node.left
else:
min_node = self._find_minimum(node.right)
node.data = min_node.data
node.right = self._delete_node_recursive(node.right, min_node.data)
return node
def _find_minimum(self, node):
while node.left is not None:
node = node.left
return node
def smallest_node(self):
if self.root is None:
return None
return self._smallest_node(self.root)
def _smallest_node(self, node):
if node.left is None:
return node
return self._smallest_node(node.left)
def largest_node(self):
if self.root is None:
return None
return self._largest_node(self.root)
def _largest_node(self, node):
if node.right is None:
return node
return self._largest_node(node.right)
def total_nodes(self):
return self._total_nodes(self.root)
def _total_nodes(self, node):
if node is None:
return 0
return self._total_nodes(node.left) + self._total_nodes(node.right) + 1
def delete_bst(self):
self.root = NonePriority queue
class PriorityQueue: def __init__(self): self.queue = []
def is_empty(self):
return len(self.queue) == 0
def size(self):
return len(self.queue)
def insert(self, item, priority):
self.queue.append((item, priority))
def delete(self):
if self.is_empty():
raise IndexError("Priority queue is empty")
highest_priority = self.queue[0][1]
highest_priority_index = 0
for i in range(1, len(self.queue)):
if self.queue[i][1] < highest_priority:
highest_priority = self.queue[i][1]
highest_priority_index = i
return self.queue.pop(highest_priority_index)[0]
def peek(self):
if self.is_empty():
raise IndexError("Priority queue is empty")
highest_priority = self.queue[0][1]
highest_priority_index = 0
for i in range(1, len(self.queue)):
if self.queue[i][1] < highest_priority:
highest_priority = self.queue[i][1]
highest_priority_index = i
return self.queue[highest_priority_index][0]Min heap
class MinHeap: def __init__(self): self.heap = []
def is_empty(self):
return len(self.heap) == 0
def size(self):
return len(self.heap)
def insert(self, item):
self.heap.append(item)
self._heapify_up(self.size() - 1)
def delete_min(self):
if self.is_empty():
raise IndexError("Heap is empty")
min_item = self.heap[0]
last_item = self.heap.pop()
if not self.is_empty():
self.heap[0] = last_item
self._heapify_down(0)
return min_item
def peek_min(self):
if self.is_empty():
raise IndexError("Heap is empty")
return self.heap[0]
def heapify_up(self, index):
self._heapify_up(index)
def heapify_down(self, index):
self._heapify_down(index)
def heap_sort(self):
sorted_list = []
while not self.is_empty():
sorted_list.append(self.delete_min())
return sorted_list
def _heapify_up(self, index):
while index > 0:
parent_index = (index - 1) // 2
if self.heap[index] < self.heap[parent_index]:
self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]
index = parent_index
else:
break
def _heapify_down(self, index):
while True:
left_child_index = 2 * index + 1
right_child_index = 2 * index + 2
smallest = index
if left_child_index < self.size() and self.heap[left_child_index] < self.heap[smallest]:
smallest = left_child_index
if right_child_index < self.size() and self.heap[right_child_index] < self.heap[smallest]:
smallest = right_child_index
if smallest != index:
self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
index = smallest
else:
break
def heap_sort(self):
sorted_list = []
while not self.is_empty():
sorted_list.append(self.delete_max())
return sorted_listMax Heap
class MaxHeap: def __init__(self): self.heap = []
def is_empty(self):
return len(self.heap) == 0
def size(self):
return len(self.heap)
def insert(self, item):
self.heap.append(item)
self._heapify_up(self.size() - 1)
def delete_max(self):
if self.is_empty():
raise IndexError("Heap is empty")
max_item = self.heap[0]
last_item = self.heap.pop()
if not self.is_empty():
self.heap[0] = last_item
self._heapify_down(0)
return max_item
def peek_max(self):
if self.is_empty():
raise IndexError("Heap is empty")
return self.heap[0]
def _heapify_up(self, index):
while index > 0:
parent_index = (index - 1) // 2
if self.heap[index] > self.heap[parent_index]:
self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]
index = parent_index
else:
break
def _heapify_down(self, index):
while True:
left_child_index = 2 * index + 1
right_child_index = 2 * index + 2
largest = index
if left_child_index < self.size() and self.heap[left_child_index] > self.heap[largest]:
largest = left_child_index
if right_child_index < self.size() and self.heap[right_child_index] > self.heap[largest]:
largest = right_child_index
if largest != index:
self.heap[index], self.heap[largest] = self.heap[largest], self.heap[index]
index = largest
else:
break
def heap_sort(self):
sorted_list = []
while not self.is_empty():
sorted_list.append(self.delete_max())
return sorted_listHash table:
class HashTable: def __init__(self): self.size = 10 self.table = [[] for _ in range(self.size)]
def _hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self._hash_function(key)
bucket = self.table[index]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
def get(self, key):
index = self._hash_function(key)
bucket = self.table[index]
for k, v in bucket:
if k == key:
return v
return None
def remove(self, key):
index = self._hash_function(key)
bucket = self.table[index]
for i, (k, v) in enumerate(bucket):
if k == key:
del bucket[i]
return
def display(self):
for i, bucket in enumerate(self.table):
print(f"Bucket {i}: {bucket}")Graph
class graph: def _init_(self): self.adjacent_list = {}
def add_vertex(self, vertex):
if vertex not in self.adjacent_list.keys():
self.adjacent_list[vertex] = []
return True
return False
def add_edge(self, vertex1, vertex2):
if vertex1 in self.adjacent_list.keys() and vertex2 in self.adjacent_list.keys():
self.adjacent_list[vertex1].append(vertex2)
self.adjacent_list[vertex2].append(vertex1)
return True
return False
def remove_edge(self, vertex1, vertex2):
if vertex1 in self.adjacent_list.keys() and vertex2 in self.adjacent_list.keys():
self.adjacent_list[vertex1].remove(vertex2)
self.adjacent_list[vertex2].remove(vertex1)
return True
return False
def remove_vertex(self, vertex):
if vertex in self.adjacent_list.keys():
for other_vertex in self.adjacent_list[vertex]:
self.adjacent_list[other_vertex].remove(vertex)
del other_vertex
return True
return False
def bfs(self,vertex):
visited = set()
visited.add(vertex)
queue = [vertex]
while queue:
current_vertex = queue.pop(0)
print(current_vertex)
for adjacent_vertex in self.adjacent_list[current_vertex]:
if adjacent_vertex not in visited:
visited.add(adjacent_vertex)
queue.append(adjacent_vertex)
def dfs(self, vertex):
visited = set()
stack = [vertex]
while stack:
current_vertex = stack.pop()
if current_vertex not in visited:
visited.add(current_vertex)
for adjacent_vertex in self.adjacent_list[vertex]:
if adjacent_vertex not in visited:
stack.append(adjacent_vertex)
def print_graph(self):
for vertex in self.adjacent_list:
print(vertex, ":", self.adjacent_list[vertex])Weighted graph
class Graph: def __init__(self): self.adjacent_list = {}
def add_vertex(self, vertex):
if vertex not in self.adjacent_list.keys():
self.adjacent_list[vertex] = []
return True
return False
def add_edge(self, vertex1, vertex2, weight):
if vertex1 in self.adjacent_list.keys() and vertex2 in self.adjacent_list.keys():
self.adjacent_list[vertex1].append((vertex2, weight))
self.adjacent_list[vertex2].append((vertex1, weight))
return True
return False
def remove_edge(self, vertex1, vertex2):
if vertex1 in self.adjacent_list.keys() and vertex2 in self.adjacent_list.keys():
self.adjacent_list[vertex1] = [(v, w) for v, w in self.adjacent_list[vertex1] if v != vertex2]
self.adjacent_list[vertex2] = [(v, w) for v, w in self.adjacent_list[vertex2] if v != vertex1]
return True
return False
def remove_vertex(self, vertex):
if vertex in self.adjacent_list.keys():
for other_vertex in self.adjacent_list[vertex]:
self.adjacent_list[other_vertex[0]] = [(v, w) for v, w in self.adjacent_list[other_vertex[0]] if v != vertex]
del self.adjacent_list[vertex]
return True
return False
def bfs(self, vertex):
visited = set()
visited.add(vertex)
queue = [vertex]
while queue:
current_vertex = queue.pop(0)
print(current_vertex)
for adjacent_vertex, _ in self.adjacent_list[current_vertex]:
if adjacent_vertex not in visited:
visited.add(adjacent_vertex)
queue.append(adjacent_vertex)
def dfs(self, vertex):
visited = set()
stack = [vertex]
while stack:
current_vertex = stack.pop()
if current_vertex not in visited:
visited.add(current_vertex)
for adjacent_vertex, _ in self.adjacent_list[current_vertex]:
if adjacent_vertex not in visited:
stack.append(adjacent_vertex)
def print_graph(self):
for vertex in self.adjacent_list:
print(vertex, ":", [v for v, _ in self.adjacent_list[vertex]])
def prim(self, start):
visited = set()
min_heap = [(0, start)]
mst = []
while min_heap:
weight, vertex = heapq.heappop(min_heap)
if vertex not in visited:
visited.add(vertex)
mst.append((weight, vertex))
for neighbor, edge_weight in self.adjacent_list[vertex]:
if neighbor not in visited:
heapq.heappush(min_heap, (edge_weight, neighbor))
print("Prim's Algorithm:")
for weight, vertex in mst:
print(f"Edge: {start} -- {vertex}, Weight: {weight}")
def kruskal(self):
parent = {}
rank = {}
mst = []
def find(parent, vertex):
if parent[vertex] == vertex:
return vertex
return find(parent, parent[vertex])
def union(parent, rank, vertex1, vertex2):
root1 = find(parent, vertex1)
root2 = find(parent, vertex2)1.Program to Search for an Element in a Binary Search Tree class Node: def _init_(self, data): self.data = data self.left = None self.right = None
def search(root, key):
# Base case: the tree is empty or the key is found at the root
if root is None or root.data == key:
return root
# Key is greater than the root's data, so search in the right subtree
if root.data < key:
return search(root.right, key)
# Key is smaller than the root's data, so search in the left subtree
return search(root.left, key)Example usage
Create the binary search tree
root = Node(5) root.left = Node(3) root.right = Node(7) root.left.left = Node(2) root.left.right = Node(4) root.right.left = Node(6) root.right.right = Node(8)
Search for an element
element = 4 result = search(root, element) if result: print(f"Element {element} found in the binary search tree.") else: print(f"Element {element} not found in the binary search tree.")
2.Program to Implement Self Balancing Binary Search Tree class TreeNode: def _init_(self, key): self.key = key self.left = None self.right = None self.height = 1
class AVLTree: def _init_(self): self.root = None
def insert(self, key):
self.root = self._insert_helper(self.root, key)
def _insert_helper(self, node, key):
if node is None:
return TreeNode(key)
elif key < node.key:
node.left = self._insert_helper(node.left, key)
else:
node.right = self._insert_helper(node.right, key)
node.height = 1 + max(self._get_height(node.left), self._get_height(node.right))
balance_factor = self._get_balance_factor(node)
if balance_factor > 1:
if key < node.left.key:
return self._rotate_right(node)
else:
node.left = self._rotate_left(node.left)
return self._rotate_right(node)
if balance_factor < -1:
if key > node.right.key:
return self._rotate_left(node)
else:
node.right = self._rotate_right(node.right)
return self._rotate_left(node)
return node
def _get_height(self, node):
if node is None:
return 0
return node.height
def _get_balance_factor(self, node):
if node is None:
return 0
return self._get_height(node.left) - self._get_height(node.right)
def _rotate_left(self, z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
z.height = 1 + max(self._get_height(z.left), self._get_height(z.right))
y.height = 1 + max(self._get_height(y.left), self._get_height(y.right))
return y
def _rotate_right(self, z):
y = z.left
T3 = y.right
y.right = z
z.left = T3
z.height = 1 + max(self._get_height(z.left), self._get_height(z.right))
y.height = 1 + max(self._get_height(y.left), self._get_height(y.right))
return y
def display(self):
self._display_helper(self.root)
def _display_helper(self, node, level=0):
if node is not None:
self._display_helper(node.right, level + 1)
print(' ' * level + '->', node.key)
self._display_helper(node.left, level + 1)tree = AVLTree() tree.insert(10) tree.insert(20) tree.insert(30) tree.insert(40) tree.insert(50) tree.insert(25)
tree.display() 3.Program to Check if a Binary Search Tree is balanced or not. class TreeNode: def _init_(self, key): self.key = key self.left = None self.right = None
def is_balanced(root): if root is None: return True
left_height = get_height(root.left)
right_height = get_height(root.right)
if abs(left_height - right_height) <= 1 and is_balanced(root.left) and is_balanced(root.right):
return True
return Falsedef get_height(node): if node is None: return 0
left_height = get_height(node.left)
right_height = get_height(node.right)
return max(left_height, right_height) + 1Example usage:
Balanced BST
root = TreeNode(10) root.left = TreeNode(5) root.right = TreeNode(15) root.left.left = TreeNode(2) root.left.right = TreeNode(8) root.right.left = TreeNode(12) root.right.right = TreeNode(20)
print(is_balanced(root)) # Output: True
Unbalanced BST
root_unbalanced = TreeNode(10) root_unbalanced.left = TreeNode(5) root_unbalanced.left.left = TreeNode(2) root_unbalanced.left.left.left = TreeNode(1)
print(is_balanced(root_unbalanced)) # Output: False
4.Program to Find the Lowest Common Ancestor of a Binary Search Tree class TreeNode: def _init_(self, key): self.key = key self.left = None self.right = None
def find_lca(root, node1, node2): if root is None: return None
# If both nodes are smaller, LCA must be in the left subtree
if root.key > node1.key and root.key > node2.key:
return find_lca(root.left, node1, node2)
# If both nodes are greater, LCA must be in the right subtree
if root.key < node1.key and root.key < node2.key:
return find_lca(root.right, node1, node2)
# If above conditions don't apply, the current node is the LCA
return rootExample usage:
Create a BST
root = TreeNode(20) root.left = TreeNode(8) root.right = TreeNode(22) root.left.left = TreeNode(4) root.left.right = TreeNode(12) root.left.right.left = TreeNode(10) root.left.right.right = TreeNode(14)
Nodes to find LCA for
node1 = TreeNode(10) node2 = TreeNode(14)
lca = find_lca(root, node1, node2) if lca is not None: print("Lowest Common Ancestor:", lca.key) else: print("Lowest Common Ancestor not found.") 5.Program to Find the Greatest Common Ancestor of a Binary Search Tree class TreeNode: def _init_(self, key): self.key = key self.left = None self.right = None
def find_gca(root, node1, node2): if root is None: return None
# If both nodes are smaller, GCA must be in the left subtree
if root.key > node1.key and root.key > node2.key:
return find_gca(root.left, node1, node2)
# If both nodes are greater, GCA must be in the right subtree
if root.key < node1.key and root.key < node2.key:
return find_gca(root.right, node1, node2)
# If one node is smaller and the other is greater, or
# one node matches the root value, the current node is the GCA
return rootExample usage:
Create a BST
root = TreeNode(20) root.left = TreeNode(8) root.right = TreeNode(22) root.left.left = TreeNode(4) root.left.right = TreeNode(12) root.left.right.left = TreeNode(10) root.left.right.right = TreeNode(14)
Nodes to find GCA for
node1 = TreeNode(10) node2 = TreeNode(14)
gca = find_gca(root, node1, node2) if gca is not None: print("Greatest Common Ancestor:", gca.key) else: print("Greatest Common Ancestor not found.")
6.Program for Spiral Order Traversal of a Tree using Recursion class Node: def init(self, data): self.right=None self.left=None self.data=data
def height(root): if root is None: return 0 else: return max(height(root.left), height(root.right))+1
def spiral(root): h=height(root) direction=1 for i in range(1, h+1): spiral_order(root, i, direction) direction = -direction
def spiral_order(root, level=1, direction=1): if root is None: return None if level==1: print(root.data,end="") elif level>1: if direction==1: spiral_order(root.left, level-1, direction) spiral_order(root.right, level-1, direction) else: spiral_order(root.right, level-1, direction) spiral_order(root.left, level-1, direction)
root=Node(1) root.left=Node(2) root.right=Node(3) root.left.left=Node(4) root.left.right=Node(5) root.right.left=Node(6) root.right.right=Node(7)
spiral(root) 7.Program to Find Deepest Left Leaf in a Binary Tree class TreeNode: def _init_(self, key): self.key = key self.left = None self.right = None
def find_deepest_left_leaf(root): max_depth = 0 deepest_left_leaf = None
def dfs(node, depth, is_left):
nonlocal max_depth, deepest_left_leaf
if node is None:
return
if is_left and node.left is None and node.right is None and depth > max_depth:
max_depth = depth
deepest_left_leaf = node
dfs(node.left, depth + 1, True)
dfs(node.right, depth + 1, False)
dfs(root, 0, False)
return deepest_left_leafExample usage:
Create a binary tree
root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5) root.right.right = TreeNode(6) root.left.right.left = TreeNode(7) root.right.right.left = TreeNode(8) root.right.right.right = TreeNode(9)
deepest_left = find_deepest_left_leaf(root) if deepest_left is not None: print("Deepest left leaf:", deepest_left.key) else: print("No left leaf found.") 8.Program to Create Mirror Image of a Binary Tree class Node: def init(self, data): self.data=data self.right=None self.left=None def mirrorimage(root): if root is None: return None else: root.left, root.right=root.right, root.left mirrorimage(root.left) mirrorimage(root.right) return def printbt(root): if root: print(root.data,"-->",end="") printbt(root.left) printbt(root.right) return print("\n")
root=Node(1) root.left=Node(2) root.right=Node(3) root.left.left=Node(4) root.left.right=Node(5) root.right.left=Node(6) root.right.right=Node(7) printbt(root) mirrorimage(root) printbt(root)
9.Program to Implement Heap class MinHeap: def _init_(self): self.heap = []
def parent(self, i):
return (i - 1) // 2
def left_child(self, i):
return 2 * i + 1
def right_child(self, i):
return 2 * i + 2
def swap(self, i, j):
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
def insert(self, item):
self.heap.append(item)
self._heapify_up(len(self.heap) - 1)
def _heapify_up(self, i):
while i != 0 and self.heap[i] < self.heap[self.parent(i)]:
self.swap(i, self.parent(i))
i = self.parent(i)
def extract_min(self):
if len(self.heap) == 0:
return None
if len(self.heap) == 1:
return self.heap.pop()
root = self.heap[0]
self.heap[0] = self.heap.pop()
self._heapify_down(0)
return root
def _heapify_down(self, i):
smallest = i
left = self.left_child(i)
right = self.right_child(i)
if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
smallest = left
if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
smallest = right
if smallest != i:
self.swap(i, smallest)
self._heapify_down(smallest)
def display(self):
print(self.heap)Example usage:
heap = MinHeap() heap.insert(10) heap.insert(20) heap.insert(15) heap.insert(30) heap.insert(25) heap.insert(5)
heap.display() # Output: [5, 10, 15, 30, 25, 20]
min_value = heap.extract_min() print(min_value) # Output: 5
heap.display() # Output: [10, 20, 15, 30, 25]
10.Program to Implement Binary Heap class BinaryHeap: def _init_(self): self.heap = [] self.size = 0
def parent(self, i):
return (i - 1) // 2
def left_child(self, i):
return 2 * i + 1
def right_child(self, i):
return 2 * i + 2
def swap(self, i, j):
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
def insert(self, item):
self.heap.append(item)
self.size += 1
self._heapify_up(self.size - 1)
def _heapify_up(self, i):
while i > 0 and self.heap[i] < self.heap[self.parent(i)]:
self.swap(i, self.parent(i))
i = self.parent(i)
def extract_min(self):
if self.size == 0:
return None
if self.size == 1:
self.size -= 1
return self.heap.pop()
root = self.heap[0]
self.heap[0] = self.heap.pop()
self.size -= 1
self._heapify_down(0)
return root
def _heapify_down(self, i):
smallest = i
left = self.left_child(i)
right = self.right_child(i)
if left < self.size and self.heap[left] < self.heap[smallest]:
smallest = left
if right < self.size and self.heap[right] < self.heap[smallest]:
smallest = right
if smallest != i:
self.swap(i, smallest)
self._heapify_down(smallest)
def display(self):
print(self.heap)Example usage:
heap = BinaryHeap() heap.insert(10) heap.insert(20) heap.insert(15) heap.insert(30) heap.insert(25) heap.insert(5)
heap.display() # Output: [5, 10, 15, 30, 25, 20]
min_value = heap.extract_min() print(min_value) # Output: 5
heap.display() # Output: [10, 20, 15, 30, 25]
Program to Implement Weak Heap class WeakHeap: def _init_(self):
self.heap = [] self.size = 0def is_empty(self):
return self.size == 0def insert(self, key):
self.heap.append(key) self.size += 1 self._heapify_up(self.size - 1)def extract_min(self):
if self.is_empty(): return None root = self.heap[0] self.heap[0] = self.heap.pop() self.size -= 1 self._heapify_down(0) return rootdef _heapify_up(self, i):
while i > 0 and self.heap[i] < self.heap[(i - 1) // 2]: self.heap[i], self.heap[(i - 1) // 2] = self.heap[(i - 1) // 2], self.heap[i] i = (i - 1) // 2def _heapify_down(self, i):
while True: left_child = 2 * i + 1 right_child = 2 * i + 2 smallest = i if left_child < self.size and self.heap[left_child] < self.heap[smallest]: smallest = left_child if right_child < self.size and self.heap[right_child] < self.heap[smallest]: smallest = right_child if smallest != i: self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i] i = smallest else: breakdef display(self):
print(self.heap)
Example usage:
heap = WeakHeap() heap.insert(10) heap.insert(20) heap.insert(15) heap.insert(30) heap.insert(25) heap.insert(5)
heap.display() # Output: [5, 10, 15, 30, 25, 20]
min_value = heap.extract_min() print(min_value) # Output: 5
heap.display() # Output: [10, 20, 15, 30, 25]
- Program to Implement Fibonacci Heap
class FibonacciHeapNode:
def _init_(self, value):
self.value = value self.parent = None self.child = None self.left = self self.right = self self.degree = 0 self.marked = False
class FibonacciHeap: def _init_(self): self.min_node = None self.size = 0
def insert(self, value):
new_node = FibonacciHeapNode(value)
if self.min_node is None:
self.min_node = new_node
else:
self._insert_node(new_node, self.min_node)
if new_node.value < self.min_node.value:
self.min_node = new_node
self.size += 1
def _insert_node(self, new_node, node):
new_node.left = node
new_node.right = node.right
node.right = new_node
new_node.right.left = new_node
def get_min(self):
if self.min_node is None:
return None
return self.min_node.value
def extract_min(self):
min_node = self.min_node
if min_node is not None:
child = min_node.child
while child is not None:
next_child = child.right
self._insert_node(child, self.min_node)
child.parent = None
child = next_child
min_node.left.right = min_node.right
min_node.right.left = min_node.left
if min_node == min_node.right:
self.min_node = None
else:
self.min_node = min_node.right
self._consolidate()
self.size -= 1
return min_node.value
def _consolidate(self):
max_degree = int(self._log(self.size) * 2) + 1
degree_table = [None] * max_degree
node = self.min_node
nodes_to_visit = [node]
while nodes_to_visit:
current = nodes_to_visit.pop()
degree = current.degree
while degree_table[degree] is not None:
other = degree_table[degree]
if current.value > other.value:
current, other = other, current
self._link(other, current)
degree_table[degree] = None
degree += 1
degree_table[degree] = current
if current != current.right:
nodes_to_visit.append(current.right)
def _link(self, child, parent):
child.left.right = child.right
child.right.left = child.left
child.parent = parent
if parent.child is None:
parent.child = child
child.right = child
child.left = child
else:
parent.child.left.right = child
child.left = parent.child.left
parent.child.left = child
child.right = parent.child
parent.degree += 1
child.marked = False
def _log(self, x):
return math.log(x) / math.log(2)
def decrease_key(self, node, new_value):
if new_value > node.value:
raise ValueError("New value is greater than the current value")
node.value = new_value
parent = node.parent
if parent is not None and node.value < parent.value:
self._cut(node, parent)
self._cascading_cut(parent)
if node.value < self.min_node.value:
self.min_node = node
def _cut(self, node, parent):
if node == node.right:
parent.child = None
else:
node.left.right = node.right
node.right.left = node.left
if parent.child == node:
parent.child = node.right
parent.degree -= 1
node.left = node
node.right = node
node.parent = None
node.marked = False
self._insert_node(node, self.min_node)def _cascading_cut(self, node): parent = node.parent if parent is not None: if not node.marked: node.marked = True else: self._cut(node, parent) self._cascading_cut(parent)
def is_empty(self): return self.size == 0
- Program to Implement Leftist Heap
class LeftistHeapNode: def _init_(self, value): self.value = value self.left = None self.right = None self.rank = 1
class LeftistHeap: def _init_(self): self.root = None
def merge(self, heap1, heap2):
if heap1 is None:
return heap2
if heap2 is None:
return heap1
if heap1.value > heap2.value:
heap1, heap2 = heap2, heap1
heap1.right = self.merge(heap1.right, heap2)
if heap1.left is None or heap1.left.rank < heap1.right.rank:
heap1.left, heap1.right = heap1.right, heap1.left
if heap1.right is None:
heap1.rank = 1
else:
heap1.rank = heap1.right.rank + 1
return heap1
def insert(self, value):
node = LeftistHeapNode(value)
self.root = self.merge(self.root, node)
def delete_min(self):
if self.root is None:
return None
min_value = self.root.value
self.root = self.merge(self.root.left, self.root.right)
return min_value
def get_min(self):
if self.root is None:
return None
return self.root.value
def is_empty(self):
return self.root is NoneExample usage
heap = LeftistHeap() heap.insert(5) heap.insert(10) heap.insert(3) heap.insert(8) heap.insert(1)
print("Min Value:", heap.get_min()) # Output: Min Value: 1
deleted_value = heap.delete_min() print("Deleted Value:", deleted_value) # Output: Deleted Value: 1
print("Min Value:", heap.get_min()) # Output: Min Value: 3
print("Is Empty:", heap.is_empty()) # Output: Is Empty: False
- Program to Implement Min Heap
class MinHeap: def _init_(self): self.heap = []
def parent(self, index):
return (index - 1) // 2
def left_child(self, index):
return (2 * index) + 1
def right_child(self, index):
return (2 * index) + 2
def swap(self, i, j):
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
def insert(self, value):
self.heap.append(value)
self.heapify_up(len(self.heap) - 1)
def heapify_up(self, index):
while index > 0 and self.heap[index] < self.heap[self.parent(index)]:
parent_index = self.parent(index)
self.swap(index, parent_index)
index = parent_index
def extract_min(self):
if len(self.heap) == 0:
return None
min_value = self.heap[0]
self.swap(0, len(self.heap) - 1)
self.heap.pop()
self.heapify_down(0)
return min_value
def heapify_down(self, index):
n = len(self.heap)
smallest = index
left = self.left_child(index)
right = self.right_child(index)
if left < n and self.heap[left] < self.heap[smallest]:
smallest = left
if right < n and self.heap[right] < self.heap[smallest]:
smallest = right
if smallest != index:
self.swap(index, smallest)
self.heapify_down(smallest)
def peek_min(self):
if len(self.heap) == 0:
return None
return self.heap[0]
def size(self):
return len(self.heap)
def display(self):
print("Min Heap:", self.heap)Example usage
heap = MinHeap() heap.insert(5) heap.insert(10) heap.insert(3) heap.insert(8) heap.insert(1)
heap.display() # Output: Min Heap: [1, 5, 3, 10, 8]
min_value = heap.extract_min() print("Extracted Min Value:", min_value) # Output: Extracted Min Value: 1
heap.display() # Output: Min Heap: [3, 5, 8, 10]
peek_value = heap.peek_min() print("Peeked Min Value:", peek_value) # Output: Peeked Min Value: 3
print("Heap Size:", heap.size()) # Output: Heap Size: 4
- Program to Implement Max Heap
class MaxHeap: def _init_(self): self.heap = []
def parent(self, index):
return (index - 1) // 2
def left_child(self, index):
return (2 * index) + 1
def right_child(self, index):
return (2 * index) + 2
def swap(self, i, j):
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
def insert(self, value):
self.heap.append(value)
self.heapify_up(len(self.heap) - 1)
def heapify_up(self, index):
while index > 0 and self.heap[index] > self.heap[self.parent(index)]:
parent_index = self.parent(index)
self.swap(index, parent_index)
index = parent_index
def extract_max(self):
if len(self.heap) == 0:
return None
max_value = self.heap[0]
self.swap(0, len(self.heap) - 1)
self.heap.pop()
self.heapify_down(0)
return max_value
def heapify_down(self, index):
n = len(self.heap)
largest = index
left = self.left_child(index)
right = self.right_child(index)
if left < n and self.heap[left] > self.heap[largest]:
largest = left
if right < n and self.heap[right] > self.heap[largest]:
largest = right
if largest != index:
self.swap(index, largest)
self.heapify_down(largest)
def peek_max(self):
if len(self.heap) == 0:
return None
return self.heap[0]
def size(self):
return len(self.heap)
def display(self):
print("Max Heap:", self.heap)Example usage
heap = MaxHeap() heap.insert(5) heap.insert(10) heap.insert(3) heap.insert(8) heap.insert(1)
heap.display() # Output: Max Heap: [10, 8, 3, 5, 1]
max_value = heap.extract_max() print("Extracted Max Value:", max_value) # Output: Extracted Max Value: 10
heap.display() # Output: Max Heap: [8, 5, 3, 1]
peek_value = heap.peek_max() print("Peeked Max Value:", peek_value) # Output: Peeked Max Value: 8
print("Heap Size:", heap.size()) # Output: Heap Size: 4
- Program to Implement Min Heap
class MinHeap: def _init_(self): self.heap = []
def parent(self, index):
return (index - 1) // 2
def left_child(self, index):
return (2 * index) + 1
def right_child(self, index):
return (2 * index) + 2
def swap(self, i, j):
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
def insert(self, value):
self.heap.append(value)
self.heapify_up(len(self.heap) - 1)
def heapify_up(self, index):
while index > 0 and self.heap[index] < self.heap[self.parent(index)]:
parent_index = self.parent(index)
self.swap(index, parent_index)
index = parent_index
def extract_min(self):
if len(self.heap) == 0:
return None
min_value = self.heap[0]
self.swap(0, len(self.heap) - 1)
self.heap.pop()
self.heapify_down(0)
return min_value
def heapify_down(self, index):
n = len(self.heap)
smallest = index
left = self.left_child(index)
right = self.right_child(index)
if left < n and self.heap[left] < self.heap[smallest]:
smallest = left
if right < n and self.heap[right] < self.heap[smallest]:
smallest = right
if smallest != index:
self.swap(index, smallest)
self.heapify_down(smallest)
def peek_min(self):
if len(self.heap) == 0:
return None
return self.heap[0]
def size(self):
return len(self.heap)
def display(self):
print("Min Heap:", self.heap)Example usage
heap = MinHeap() heap.insert(5) heap.insert(10) heap.insert(3) heap.insert(8) heap.insert(1)
heap.display() # Output: Min Heap: [1, 5, 3, 10, 8]
min_value = heap.extract_min() print("Extracted Min Value:", min_value) # Output: Extracted Min Value: 1
heap.display() # Output: Min Heap: [3, 5, 8, 10]
peek_value = heap.peek_min() print("Peeked Min Value:", peek_value) # Output: Peeked Min Value: 3
print("Heap Size:", heap.size()) # Output: Heap Size: 4
17.Program to Print the Nodes at Odd Levels of a Tree class Node: def init(self, data): self.right=None self.left=None self.data=data
def oddNode(root,level): if root is None: return 0 else: if(level%2!=0): print(root.data) oddNode(root.left,level+1) oddNode(root.right,level+1)
root=Node(5) root.left=Node(3) root.right=Node(9) root.left.left=Node(4) root.left.right=Node(1) oddNode(root,1)
- Program to Create Expression Tree from Infix Expression
class Node: def _init_(self, value): self.value = value self.left = None self.right = None
def is_operator(char): return char in ['+', '-', '*', '/']
def precedence(char): if char == '+' or char == '-': return 1 elif char == '*' or char == '/': return 2 else: return 0
def infix_to_postfix(expression): postfix = [] stack = []
for char in expression:
if char.isalnum():
postfix.append(char)
elif char == '(':
stack.append(char)
elif char == ')':
while stack and stack[-1] != '(':
postfix.append(stack.pop())
stack.pop() # Discard '('
elif is_operator(char):
while stack and stack[-1] != '(' and precedence(char) <= precedence(stack[-1]):
postfix.append(stack.pop())
stack.append(char)
while stack:
postfix.append(stack.pop())
return ''.join(postfix)def build_expression_tree(postfix): stack = []
for char in postfix:
if char.isalnum():
node = Node(char)
stack.append(node)
elif is_operator(char):
right = stack.pop()
left = stack.pop()
node = Node(char)
node.left = left
node.right = right
stack.append(node)
return stack.pop()def inorder_traversal(root): if root is None: return
inorder_traversal(root.left)
print(root.value, end=' ')
inorder_traversal(root.right)Example usage
expression = "a+bc-(d/e+fg)"
postfix = infix_to_postfix(expression) print("Postfix expression:", postfix)
root = build_expression_tree(postfix)
print("Inorder traversal of the expression tree:") inorder_traversal(root)
19.Program to find Height of a binary tree class Node: def init(self, data): self.right=None self.left=None self.data=data def height(root): if root is None: return 0 else: left=height(root.left) right=height(root.right) return 1+max(left, right)
root=Node(5) root.left=Node(3) root.right=Node(9) root.left.left=Node(4) root.left.right=Node(1) val=height(root) print("Height of tree =",val) 20.Program to calculate & display Product of all leaf nodes of binary tree class Node: def init(self, data): self.right=None self.left=None self.data=data def product(root): if root is None: return 0 else: if root.left is None and root.right is None: L.append(root.data) product(root.left) product(root.right) root=Node(5) root.left=Node(9) root.right=Node(4) root.left.left=Node(3) root.left.right=Node(5) L=[] p=1 product(root) for i in L: p=p*i print(p)
- Program to Find kth maximum and kth minimum value in a binary search tree
class Node: def _init_(self, value): self.value = value self.left = None self.right = None
def inorder_traversal(root, values): if root is None: return
inorder_traversal(root.left, values)
values.append(root.value)
inorder_traversal(root.right, values)def find_kth_maximum(values, k): if k > len(values) or k < 1: return None
return values[-k]def find_kth_minimum(values, k): if k > len(values) or k < 1: return None
return values[k - 1]Example usage
BST
root = Node(4) root.left = Node(2) root.right = Node(6) root.left.left = Node(1) root.left.right = Node(3) root.right.left = Node(5) root.right.right = Node(7)
Find kth maximum and kth minimum
values = [] inorder_traversal(root, values)
k = 3 kth_maximum = find_kth_maximum(values, k) kth_minimum = find_kth_minimum(values, k)
print(f"{k}th maximum value: {kth_maximum}") print(f"{k}th minimum value: {kth_minimum}")
- Program to Convert BST to min-heap
class Node: def _init_(self, value): self.value = value self.left = None self.right = None
def inorder_traversal(root, values): if root is None: return
inorder_traversal(root.left, values)
values.append(root.value)
inorder_traversal(root.right, values)def build_min_heap(values, root): if root is None: return None
root.value = values.pop(0)
root.left = build_min_heap(values, root.left)
root.right = build_min_heap(values, root.right)
return rootdef convert_bst_to_min_heap(root): values = [] inorder_traversal(root, values)
return build_min_heap(values, root)def print_inorder(root): if root is None: return
print_inorder(root.left)
print(root.value, end=' ')
print_inorder(root.right)Example usage
BST
root = Node(4) root.left = Node(2) root.right = Node(6) root.left.left = Node(1) root.left.right = Node(3) root.right.left = Node(5) root.right.right = Node(7)
Convert BST to min-heap
converted_root = convert_bst_to_min_heap(root)
Print the inorder traversal of the converted min-heap
print("Inorder traversal of the converted min-heap:") print_inorder(converted_root)
- Program to combine two binary search trees into a single tree
class Node: def _init_(self, value): self.value = value self.left = None self.right = None
def inorder_traversal(root, values): if root is None: return
inorder_traversal(root.left, values)
values.append(root.value)
inorder_traversal(root.right, values)def create_bst_from_sorted(values, start, end): if start > end: return None
mid = (start + end) // 2
root = Node(values[mid])
root.left = create_bst_from_sorted(values, start, mid - 1)
root.right = create_bst_from_sorted(values, mid + 1, end)
return rootdef combine_bsts(root1, root2): values1 = [] values2 = []
inorder_traversal(root1, values1)
inorder_traversal(root2, values2)
combined_values = sorted(values1 + values2)
return create_bst_from_sorted(combined_values, 0, len(combined_values) - 1)def print_inorder(root): if root is None: return
print_inorder(root.left)
print(root.value, end=' ')
print_inorder(root.right)Example usage
Tree 1
root1 = Node(4) root1.left = Node(2) root1.right = Node(5) root1.left.left = Node(1) root1.left.right = Node(3)
Tree 2
root2 = Node(7) root2.left = Node(6) root2.right = Node(8)
Combine the trees
combined_root = combine_bsts(root1, root2)
Print the combined tree
print("Inorder traversal of the combined tree:") print_inorder(combined_root)
24.Program to Count number of nodes in a binary tree class Node: def init(self, data): self.left=None self.right=None self.data=data
def count(root): if root is None: return 0 else: return 1+count(root.left)+count(root.right)
root=Node(5) root.left=Node(2) root.right=Node(4) root.left.left=Node(5) root.left.right=Node(3) val=count(root) print("count = ",val) 25.
- Program to remove all nodes which don’t line in any path with sum >= K.
class Node: def _init_(self, value): self.value = value self.left = None self.right = None
def remove_nodes(root, k): if root is None: return None
root.left = remove_nodes(root.left, k)
root.right = remove_nodes(root.right, k)
if root.left is None and root.right is None:
if root.value < k:
return None
return rootdef print_tree(root): if root is None: return
print_tree(root.left)
print(root.value, end=' ')
print_tree(root.right)Example usage
root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) root.right.right = Node(7)
k = 6
print("Original tree:")