Question

Please based on my python code. do the following steps:

thank you

1. Develop a method build_bst which takes a list of data (example: [6, 2, 4, 22, 34, 9, 6, 67, 42, 55, 70, 120, 99, 200]) and builds a binary search tree full of Node objects appropriately arranged.
2. Test your build_bst with different sets of inputs similar to the example provided above. Show 3 different examples.
3. Choose 1 example data.  Develop a function to remove a node from a bst data structure.  This function should consider all the three cases:  case-1: remove a leaf node, case-2: remove a node with one child and case-3: remove a node with two children. Show an example.

Perform tree balancing after node deletion if necessary.You can choose AVL tree or Red Black tree implementation.

Perform the time complexity for this function.Briefly explain?

4. Write a function which takes two bst and merges the two trees.  The function should return the merged tree.  Show an example.

Perform tree balancing after merge a tree if necessary.You can choose AVL tree or Red Black tree implementation.

Perform the time complexity for this function.

Here is my python code:

from queue import Queue

class Node:

def __init__(self, data):

self.parent = None

self.left = None

self.right = None

if isinstance(data, list):

self.build_tree(data)

return

self.value = data

def build_tree(self, L):

q = Queue()

q.put(self)

self.value = L[0]

for i in range(1, len(L), 2):

node = q.get()

node.left = Node(L[i])

node.left.parent = node

q.put(node.left)

if i+1 == len(L):

return

node.right = Node(L[i+1])

node.right.parent = node

q.put(node.right)

def min(self):

if self.left is None or self.right is None:

if self.left is not None:

return min(self.value, self.left.min())

if self.right is not None:

return min(self.value, self.right.min())

return self.value

return min(self.value, self.left.min(), self.right.min())

def max(self):

if self.left is None or self.right is None:

if self.left is not None:

return max(self.value, self.left.max())

if self.right is not None:

return max(self.value, self.right.max())

return self.value

return max(self.value, self.left.max(), self.right.max())

def preorder(self):

if self.value is None:

return

print(self.value, end=' ')

if self.left is not None:

self.left.preorder()

if self.right is not None:

self.right.preorder()

if __name__ == "__main__":

#L = [6, 2, 4, 22, 34, 9, 6, 67, 42, 55, 70, 120, 99, 200]

L = [int(x) for x in input().split()]

root = Node(L)

root.preorder()

print()

print(f"Minimum node in tree: {root.min()}")

print(f"Maximum node in tree: {root.max()}")

Answer 1

Time Complexity of the performed below algorithm is dependent on the height of the bst tree, hence O(h), where h is the height of the tree.
However, the worst case time complexity is O(n).

PYTHON CODE:

class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
  
  
  
def inorder(root):
if root!=None:
inorder(root.left)
print(root.key,end=" ")
inorder(root.right)

def build_bst(node, key):
if (node==None):
return Node(key)

if (key<node.key):
node.left = build_bst(node.left, key)
else:
node.right = build_bst(node.right, key)
return node

def minValueNode(node):
current = node
while(current.left is not None):
current = current.left
return current

def deleteNode(root, key):

if (root==None):
return root
if (key < root.key):
root.left = deleteNode(root.left, key)
elif(key > root.key):
root.right = deleteNode(root.right, key)
else:
if(root.left== None) :
temp = root.right
root = None
return temp
  
elif (root.right == None) :
temp = root.left
root = None
return temp
  
temp = minValueNode(root.right)
root.key = temp.key
root.right = deleteNode(root.right , temp.key)
return root

root = None
#L = [6 2 4 22 34 9 6 67 42 55 70 120 99 200]

L = list(map(int,input("Enter the elements:").split()))

for i in range(len(L)):
root=build_bst(root,L[i])

print ("\nInorder traversal")
inorder(root)

print ("\n\nCASE I: Deletion of leaf node")
root = deleteNode(root, 200)
print ("Modified Inorder traversal:")
inorder(root)

print ("\n\nCASE II: Deletion of a node with one child")
root = deleteNode(root, 42)
print ("Modified Inorder traversal:")
inorder(root)

print ("\n\nCASE III: Deletion of a node with two children")
root = deleteNode(root, 120)
print ("Modified Inorder traversal:")
inorder(root)