1. You will implement a k-ary tree that stores an arbitrary type (which will be given at the construction of k-ary tree) of data in Tree.java file. You must
implement the following methods as well as its constructor: root: Return the root node of the tree.
add: Insert the given node at the possible rightmost slot of lowest depth and return the inserted node.
detach: Detach the given node from the tree.
preorder: Return the sequence of items visited by preorder traversal. postorder: Return the sequence of items visited by postorder traversal. arity: Return k.
size: Return the size of the tree.
height: Return the height of the tree.
isEmpty: Return whether the tree is empty or not.
2.You are asked to find an item with minimum value from the item stream. You must implement the following methods as well as its constructor in
StreamMin.java file:
add: Add a given item into the structure.
findMin: Return the item with minimum value from the structure.
extractMin: Return and remove the item with minimum value from the structure.
size: Return the number of items.
isEmpty: Return whether the structure is empty or not. reset: Remove all the items from the structure.
Note that add, findMin, extractMin must run in O(log n) time and size, isEmpty must run in O(1) time. (regardless to the number of items the structure has). You also need to implement StreamMin using Tree from the first part.