About
class Node: def __init__(self, data): self.data = data self.left = None self.right = None
class BST: def __init__(self): self.root = None
def insert(self, data):
if self.root is None:
self.root = Node(data)
else:
prev = None
current = self.root
while current is not None:
if current.data > data:
prev = current
current = current.left
elif current.data < data:
prev = current
current = current.right
if prev.data > data:
prev.left = Node(data)
return
elif prev.data < data:
prev.right = Node(data)
return
def search(self, data):
if self.root is None:
return
elif self.root.data == data:
return True
else:
p = self.root
while p is not None:
if p.data > data:
p = p.left
elif p.data < data:
p = p.right
elif p.data == data:
return True
return False
def check_balanced(self, root):
if root is None:
return True
else:
if self.get_factor(root.left) - self.get_factor(root.right) in [-1, 0, 1]:
return self.check_balanced(root.left) and self.check_balanced(root.right)
else:
return False
def getSortOrder(self,root,li):
if root:
self.getSortOrder(root.left,li)
li.append(root.data)
self.getSortOrder(root.right,li)
def k_max_n_min(self,root,k):
if self.root is None:
return
elif k<=0:
return
else:
li = []
self.getSortOrder(root,li)
print(li)
if k>len(li):
return
else:
print("minimum: ",li[k-1])
print("maximum: ",li[-k])
def print_odd_levels(self):
if self.root is None:
return
else:
q = [self.root]
level=1
while q:
level_size = len(q)
current = []
for _ in range(level_size):
node = q.pop(0)
current.append(node.data)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
if level%2==1:
print(current)
level+=1
def get_height(self, root):
if root is None:
return 0
else:
left_height = self.get_height(root.left)
right_height = self.get_height(root.right)
return max(left_height, right_height)+1
def get_spiral_order(self):
if self.root is None:
return
elif self.root.left is None and self.root.right is None:
print(self.root.data)
else:
q = [self.root]
level = 1
while q:
level_size = len(q)
current = []
for _ in range(level_size):
node = q.pop(0)
current.append(node.data)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
if level % 2:
print(current[::-1])
else:
print(current)
level+=1
def get_lca(self,root,node1,node2):#assuming both the nodes are present
if root is None:
return
elif root.data == node1 or root.data == node2:
return root.data
elif node1 == node2:
return node1
elif root.data < node1 and root.data < node2:
root = root.right
return self.get_lca(root,node1,node2)
elif root.data > node1 and root.data > node2:
root = root.left
return self.get_lca(root,node1,node2)
elif (root.data > node1 and root.data < node2) or (root.data > node2 and root.data < node1):
return root.data
def deepest(self):
if self.root is None:
return
elif self.root.left is None and self.root.right is None:
return self.root.data
else:
q = [self.root]
left_most = self.root
while q:
level_size = len(q)
for _ in range(level_size):
node = q.pop(0)
if _ == 0:
left_most = node.data
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return left_most
def get_balance_factor(self, p):
if p is None:
return 0
else:
left_height = self.get_factor(p.left)
right_height = self.get_factor(p.right)
return max(left_height, right_height) + 1
def mirror(self,p):
if p:
p.left,p.right = p.right,p.left
self.mirror(p.left)
self.mirror(p.right)
def get_traversal(self, p, li):
if p:
self.get_traversal(p.left, li)
li.append(p.data)
self.get_traversal(p.right, li)
def do_pre_order(self, p, li):
if p:
p.data = li.pop(0)
self.do_pre_order(p.left, li)
self.do_pre_order(p.right, li)
def convert_to_minHeap(self, p):
if p is None:
return
else:
li = []
self.get_traversal(p, li)
self.do_pre_order(p, li)
def number_of_nodes(self, p):
if p:
return 1+self.number_of_nodes(p.left)+self.number_of_nodes(p.right)
else:
return 0
def get_product(self,p):
if p:
if p.left is None and p.right is None:
return p.data
elif p.left is not None and p.right is not None:
return self.get_product(p.left)*self.get_product(p.right)
elif p.left is not None:
return self.get_product(p.left)
else:
return self.get_product(p.right)if __name__ == "__main__": li = [234,45346,45,64,756,875,246,75] t = BST() for i in li: t.insert(i) t.k_max_n_min(t.root,0)
class MinHeap:
def __init__(self):
self.li = []
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 insert(self, data):
self.li.append(data)
self.heapify_up(len(self.li)-1)
def extract_min(self):
if not len(self.li):
return
elif len(self.li)==1:
return self.li.pop()
else:
min_value = self.li[0]
self.li[0] = self.li.pop()
self.heapify_down(0)
return min_value
def heapify_up(self, index):
if index>0 and self.li[self.parent(index)] > self.li[index]:
self.li[self.parent(index)],self.li[index] = self.li[index], self.li[self.parent(index)]
self.heapify_up(self.parent(index))
def heapify_down(self,index):
left_child = 2*index+1
right_child = 2*index+2
smallest = index
if left_child < len(self.li) and self.li[left_child] < self.li[smallest]:
smallest = left_child
if right_child < len(self.li) and self.li[right_child] < self.li[smallest]:
smallest = right_child
if smallest!=index:
self.li[smallest],self.li[index] = self.li[index],self.li[smallest]
self.heapify_down(smallest)
if __name__ == "__main__":
li = [5,3,8,1,10]
h = MinHeap()
for i in li:
h.insert(i)
print(h.li)
class MaxHeap:
def __init__(self):
self.heap = []
def insert(self, item):
self.heap.append(item)
self._heapify_up(len(self.heap) - 1)
def extract_max(self):
if len(self.heap) == 0:
return None
if len(self.heap) == 1:
return self.heap.pop()
max_value = self.heap[0]
self.heap[0] = self.heap.pop()
self._heapify_down(0)
return max_value
def _heapify_up(self, index):
parent_index = (index - 1) // 2
if parent_index >= 0 and self.heap[parent_index] < self.heap[index]:
self.heap[parent_index], self.heap[index] = self.heap[index], self.heap[parent_index]
self._heapify_up(parent_index)
def _heapify_down(self, index):
left_child_index = 2 * index + 1
right_child_index = 2 * index + 2
largest = index
if left_child_index < len(self.heap) and self.heap[left_child_index] > self.heap[largest]:
largest = left_child_index
if right_child_index < len(self.heap) and self.heap[right_child_index] > self.heap[largest]:
largest = right_child_index
if largest != index:
self.heap[largest], self.heap[index] = self.heap[index], self.heap[largest]
self._heapify_down(largest)
# Example usage:
heap = MaxHeap()
heap.insert(5)
heap.insert(3)
heap.insert(8)
heap.insert(1)
heap.insert(10)
print(heap.heap) # Output: [10, 5, 8, 1, 3]
max_value = heap.extract_max()
print(heap.heap) # Output: [8, 5, 3, 1]
class Node: def __init__(self, data): self.data = data self.left = None self.right = None
class BST: def __init__(self): self.root = None
def insert(self, data):
if self.root is None:
self.root = Node(data)
else:
prev = None
p = self.root
while p is not None:
if p.data > data:
prev = p
p = p.left
elif p.data < data:
prev = p
p = p.right
if prev.data > data:
prev.left = Node(data)
return
elif prev.data < data:
prev.right = Node(data)
return
def inorder(self, p):
if p:
self.inorder(p.left)
print(p.data, end=' ')
self.inorder(p.right)
def get_traversal(self, p, li):
if p:
self.get_traversal(p.left, li)
li.append(p.data)
self.get_traversal(p.right, li)
def do_pre_order(self, p, li):
if p:
p.data = li.pop(0)
self.do_pre_order(p.left, li)
self.do_pre_order(p.right, li)
def convert_to_minHeap(self, p):
if p is None:
return
else:
li = []
self.get_traversal(p, li)
self.do_pre_order(p, li)if __name__ == "__main__": li = [345, 36, 45, 656, 7, 234] t = BST() for i in li: t.insert(i)