Republic of the Philippines
University of Cabuyao
Pamantasan ng Cabuyao
College of Engineering
Katapatan Mutual Homes, Brgy. Banay-banay, City of Cabuyao, Laguna, Phillippines 4025
DATA STRUTURES AND ALGORITHMS
LABORATORY ACTIVITY 4 FINALS
SUBMITTED BY:
Toong, Mark John R. - 2203131
SUBMITTED TO:
Engr. Cherry Casuat
INSTRUCTOR
DATE OF SUBMISSION:
January 5, 2024
Republic of the Philippines
University of Cabuyao
Pamantasan ng Cabuyao
College of Engineering
Katapatan Mutual Homes, Brgy. Banay-banay, City of Cabuyao, Laguna, Phillippines 4025
MACHINE PROBLEM
CODE:
class BSTNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.parent = None
def insert(self, node):
if node.key < self.key:
if self.left is None:
self.left = node
node.parent = self
else:
self.left.insert(node)
elif node.key > self.key:
if self.right is None:
self.right = node
node.parent = self
else:
self.right.insert(node)
def inorder(self):
result = []
if self.left:
result.extend(self.left.inorder())
result.append(self.key)
if self.right:
result.extend(self.right.inorder())
return result
def replace_node_of_parent(self, new_node):
if self.parent:
if self.parent.left == self:
self.parent.left = new_node
else:
self.parent.right = new_node
if new_node:
new_node.parent = self.parent
def find_min(self):
current = self
Republic of the Philippines
University of Cabuyao
Pamantasan ng Cabuyao
College of Engineering
Katapatan Mutual Homes, Brgy. Banay-banay, City of Cabuyao, Laguna, Phillippines 4025
while current.left:
current = current.left
return current
def remove(self):
if self.left and self.right:
successor = self.right.find_min()
self.key = successor.key
successor.remove()
elif self.left or self.right:
child = self.left or self.right
self.replace_node_of_parent(child)
else:
self.replace_node_of_parent(None)
def search(self, key):
if key == self.key:
return self
elif key < self.key and self.left:
return self.left.search(key)
elif key > self.key and self.right:
return self.right.search(key)
else:
return None
class BSTree:
def __init__(self):
self.root = None
def inorder(self):
if self.root:
return self.root.inorder()
return []
def add(self, key):
new_node = BSTNode(key)
if self.root is None:
self.root = new_node
else:
self.root.insert(new_node)
def search(self, key):
if self.root:
return self.root.search(key)
return None
def remove(self, key):
node_to_remove = self.search(key)
if node_to_remove:
Republic of the Philippines
University of Cabuyao
Pamantasan ng Cabuyao
College of Engineering
Katapatan Mutual Homes, Brgy. Banay-banay, City of Cabuyao, Laguna, Phillippines 4025
node_to_remove.remove()
def print_menu():
print("****************BINARY SEARCH TREE****************")
print("* Programmed by: Toong, Mark John R. *")
print("* *")
print("* < < < MAIN MENU > > > *")
print("* *")
print("* ADD <KEYS> *")
print("* REMOVE <KEYS> *")
print("* INORDER TRAVERSAL *")
print("* EXIT PROGRAM *")
print("* *")
print("**************************************************")
def main():
bstree = BSTree()
menu_shown = False
while True:
if not menu_shown:
print_menu()
menu_shown = True
user_input = input("What would you like to do? ").split()
command = user_input[0].upper()
if command == "ADD" and len(user_input) == 2:
key = int(user_input[1])
bstree.add(key)
elif command == "REMOVE" and len(user_input) == 2:
key = int(user_input[1])
bstree.remove(key)
elif command == "INORDER" and len(user_input) == 1:
print("Inorder traversal:", " ".join(map(str, bstree.inorder())))
elif command == "EXIT" and len(user_input) == 1:
break
else:
print("Invalid command. Please try again.")
if __name__ == "__main__":
main()
Republic of the Philippines
University of Cabuyao
Pamantasan ng Cabuyao
College of Engineering
Katapatan Mutual Homes, Brgy. Banay-banay, City of Cabuyao, Laguna, Phillippines 4025
OUTPUT:
Republic of the Philippines
University of Cabuyao
Pamantasan ng Cabuyao
College of Engineering
Katapatan Mutual Homes, Brgy. Banay-banay, City of Cabuyao, Laguna, Phillippines 4025
Write a Python program which allows the user to input the in-order and post-order
traversal of the same binary tree, then the program will print the corresponding:
CODE:
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def build_tree(inorder, postorder):
if not inorder or not postorder:
return None
root_value = postorder.pop()
root = TreeNode(root_value)
inorder_index = inorder.index(root_value)
root.right = build_tree(inorder[inorder_index + 1:], postorder)
root.left = build_tree(inorder[:inorder_index], postorder)
return root
def inorder_traversal(root):
result = []
if root:
result += inorder_traversal(root.left)
result.append(root.value)
result += inorder_traversal(root.right)
return result
def postorder_traversal(root):
result = []
if root:
result += postorder_traversal(root.left)
result += postorder_traversal(root.right)
result.append(root.value)
return result
def preorder_traversal(root):
result = []
if root:
result.append(root.value)
result += preorder_traversal(root.left)
result += preorder_traversal(root.right)
return result
Republic of the Philippines
University of Cabuyao
Pamantasan ng Cabuyao
College of Engineering
Katapatan Mutual Homes, Brgy. Banay-banay, City of Cabuyao, Laguna, Phillippines 4025
# Get user input for in-order and post-order traversals
inorder_input = input("Enter in-order traversal (comma-separated values):
").split(',')
postorder_input = input("Enter post-order traversal (comma-separated values):
").split(',')
# Convert input values to integers
inorder = [int(x) for x in inorder_input]
postorder = [int(x) for x in postorder_input]
# Build the binary tree
root = build_tree(inorder, postorder)
# Calculate and print the corresponding traversals
print("Inorder traversal is:", inorder_traversal(root))
print("Post-order traversal is:", postorder_traversal(root))
print("Preorder traversal is:", preorder_traversal(root))
OUTPUT:
