Python

Task $1$: BST Class Implementation

Define a class named BinarySearchTree with the following methods:

$-$ insert$($self$,$ value$)$: Add an element to the tree.

$-$ delete$($self$,$ value$)$: Remove a node with the specified integer value from the tree.

$-$ search$($self$,$ value$)$: Find a specific element in the tree.

$-$ in$\_$order$\_$traversal$($self$)$: display all elements in the tree in in$-$order$($sorted order$).$

$-$ pre$\_$order$\_$traversal$($self$)$: display all elements in the tree in pre$-$order.

$-$ post$\_$order$\_$traversal$($self$)$: display all elements in the tree in post$-$order.

$-$ height$($self$)$: Return the height of the tree.

Task $2$: BST Operations and Function Testing

After implementing the BinarySearchTree class, test all its methods using a sequence of operations:

$-$ Insertion and Basic Structure:

$--$Generate a list of $64$ unique random integers within the range $[1,128].$

$--$Insert each integer into the BST$.$ After all insertions, print the tree's height.

$-$Search Operations:

$--$Search for specific values $($first$,$ middle, and last in your list$)$ in the BST$.$ Print the outcome of each search.

$-$Traversal Outputs:

$--$Print the results of the in$-$order, pre$-$order, and post$-$order traversals.

$-$Deletion and Structure Adjustment:

$--$Delete specific values $($first$,$ middle, and last in your list$)$ from the BST$.$

$--$After each deletion, print the tree's height and the in$-$order traversal.

$-$Final Tree Height:

$--$Print the final height of the BST after all modifications.

Task $3$: Testing with Different Data Sets

Conduct tests on multiple data sets to analyze the BST under different conditions:

$-$Varied Size Data Sets:

$--256$ Integers: Generate $256$ unique random integers within $[1,512].$

$--128$ Integers: Generate $128$ unique random integers within $[1,256].$

$--64$ Integers: Generate $64$ unique random integers within $[1,128].$

$-$ Worst$-$Case Scenario Test:

$--$Use an ascending sequence $($e$.$g$.,[1,2,3,...,$ N$])$ to simulate the worst$-$case input and examine the tree's height and structure.

$--$Use an ascending sequence $[1,2,3,...,64]$

$--$Use an ascending sequence $[1,2,3,...,128]$

$--$Use an ascending sequence $[1,2,3,...,256]$

$-$For each data set:

$-$Insert the numbers into a fresh BST instance.

$-$Print the in$-$order traversal results and the tree's height.

$-$Optionally, measure and compare the time taken for various operations.

Task $4$: Comparative Analysis and Discussions

$-$For each data set tested, including the worst$-$case scenario, note the tree height and summarize any structural changes.

$-$Write a discussion on the operational differences observed in the BST for average$-$case and worst$-$case inputs. Discuss any trends or behaviors in the height of the trees.