Project 6: Binary Search Tree (C++)

The purpose of this assignment is to practice:

• Implement a binary search tree structure
• Demonstrate tree traversals
• Analyze and compare algorithms for efficiency using Big-O notation

For this assignment, you will implement a binary search tree and use it to store a large text file. Your program should read text from a file and insert each word in a binary search tree. Do not store duplicate text.

Once the tree is populated, print the contents of the tree using an in-order traversal. Next, allow the user to enter words to search for. For each word entered, your program should report the number of elements inspected and whether or not the word was located. Next, allow the user to enter words to remove from the tree. After each removal, print the contents of the tree.

Heres a sample run:

Provide an analysis of remove and search algorithms using Big-O notation

Show transcribed image text

Want the answer in C++. Please show the output.

are, been, birds, did, even, fish, for, hear, heard?, hot, i, it's, just, like, mosquitoes, now, on, rising, river, seven, speak, the, there's, to, too, up, weeks, what, you, Enter string, enter -1 to quit: honey Inspected 9 elements 'honey' not in tree Enter string, enter -1 to quit: fish Inspected 2 elements 'fish' located Enter string, enter -1 to quit: birds Inspected 4 elements 'birds' located Enter string, enter -1 to quit: there's Inspected o elements 'there's' located Enter string, enter -1 to quit: -1 Enter string to remove: too are, been, birds, did, even, fish, for, hear, heard?, hot, i, it's, just, like, mosquitoes, now, on, rising, river, seven, speak, the, there's, to, up, weeks, what, you, Enter string to remove: even are, been, birds, did, fish, for, hear, heard?, hot, i, it's, just, like, mosquitoes, now, on, rising, river, seven, speak, the, there's, to, up, weeks, what, you, Enter string to remove: quit are, been, birds, did, fish, for, hear, heard?, hot, i, it's, just, like, mosquitoes, now, on, rising, river, seven, speak, the, there's, to, up, weeks, what, you, Enter string to remove: -1