$1.$ Implement a BST Class

Create a Node class that represents a node in a binary tree with:

o data: the value stored at the node.

o left: the left child.

o right: the right child.

Then, create a BST class with the following functions:

a$.$ Insert: A method insert$($self$,$ value$)$ to insert a value into the BST$.$

b$.$ Find: A method find$($self$,$ value$)$ that returns the node if it exists in the tree

or None if it doesn't.

$2.$ Delete a Node

Implement a method delete$($self$,$ value$)$ to remove a node from the BST$.$ Ensure you

handle all three cases:

o Node to be deleted has no children $($leaf node$).$

o Node to be deleted has one child.

o Node to be deleted has two children $($replace it with its in$-$order successor or

predecessor$).$

$3.$ Pre$-$order Traversal

Write a method pre$\_$order$\_$traversal$($self$)$ that performs a pre$-$order traversal of the

tree $($root $->$ left $->$ right$)$ and prints the values in this order.

$4.$ Main Program

Write a main program that:

o Creates an empty BST$.$

o Inserts the following values into the tree: $50,30,70,20,40,60,80.$

o Deletes the node with value $30($a node with two children$).$

o Deletes the node with value $20($a leaf node$).$

o Deletes the node with value $70($a node with one child$).$

o Finds the node with value $60.$

o Prints the pre$-$order traversal of the tree after each deletion