Implement a Binary Search Tree data structure in C++. Your binary search tree will store integers. (For convenience, you may store the data directly in the linknode if you wish.) Your binary search tree should implement the following public functions:

• search(key)
• insert(key)
• delete(key)
• min
• max
• predecessor(key)
• successor(key)
• inorder traversal
• preorder traversal
• postorder traversal

You should also implement, at your discretion, any helper or wrapper functions. You may assume that the key values are unique.

INPUT

Create a main program that reads a "session trace" from STDIN and sends output to STDOUT. The input will contain (at most) one operation per line. Apply, in order, each of the operations to an object of your bst class. Ignore any comments in the input. A comment begins with a pound sign ("#") and continues to the end of the line.

SAMPLE RUN

an input session trace matching output session trace 

OUTPUT

Each of the following functions should generate output (one per line)

• The search function should output "key found." or "key not found."
• Insert should output "inserted key."
• Delete should remove an object with the given key value from the tree and output "deleted key." or "delete key - not found." depending on the result.
• Min and Max should output "min is key." or "max is key." or "tree empty."
• Predecessor should output "key predecessor is key." or "no predecessor for key." or "key not in tree." Successor should function similarly.
• The three traversal functions should output "inorder traversal: " (or "postorder traversal: " or "preorder traversal: ") followed by a space separated list of elements starting on the next line.

# Sample data file for BST Program # pound sign indicates comment until end-of-line ################################################# # insert some values insert 20 insert 30 insert 12 insert 5 insert 4 insert 1 insert 2 insert 3 insert 50 insert 70 insert 60 insert 65 insert 62 insert 61 insert 100 insert 80 insert 91 insert 92 insert 93 insert 140 insert 120 insert 130 insert 22 insert 23 insert 24 insert 33 insert 34 insert 35 insert 19 insert 17 insert 16 insert 13 insert 14 insert 15 # test some stuff search 20 search 21 search 130 predecessor 20 predecessor 30 predecessor 80 predecessor 1 min max inorder # delete some values delete 20 delete 21 delete 22 delete 30 delete 31 delete 32 delete 12 delete 15 delete 1 delete 140 delete 130 # test some stuff search 20 search 65 search 130 min max successor 24 successor 25 successor 120 successor 100 postorder preorder # done with input

Output session trace

inserted 20. inserted 30. inserted 12. inserted 5. inserted 4. inserted 1. inserted 2. inserted 3. inserted 50. inserted 70. inserted 60. inserted 65. inserted 62. inserted 61. inserted 100. inserted 80. inserted 91. inserted 92. inserted 93. inserted 140. inserted 120. inserted 130. inserted 22. inserted 23. inserted 24. inserted 33. inserted 34. inserted 35. inserted 19. inserted 17. inserted 16. inserted 13. inserted 14. inserted 15. 20 found. 21 not found. 130 found. 20 predecessor is 19. 30 predecessor is 24. 80 predecessor is 70. no predecessor for 1. min is 1. max is 140. inorder traversal: 1 2 3 4 5 12 13 14 15 16 17 19 20 22 23 24 30 33 34 35 50 60 61 62 65 70 80 91 92 93 100 120 130 140 deleted 20. delete 21 - not found. deleted 22. deleted 30. delete 31 - not found. delete 32 - not found. deleted 12. deleted 15. deleted 1. deleted 140. deleted 130. 20 not found. 65 found. 130 not found. min is 2. max is 120. 24 successor is 33. 25 not in tree. no successor for 120. 100 successor is 120. postorder traversal: 3 2 4 5 14 16 17 19 13 24 35 34 61 62 65 60 93 92 91 80 120 100 70 50 33 23 preorder traversal: 23 13 5 4 2 3 19 17 16 14 33 24 50 34 35 70 60 65 62 61 100 80 91 92 93 120