Description
In this Quiz you need to do several steps of Binary Tree manipulation to get the desired output. Refer to the following instructions regarding the functions that you need to implement.
Insert [index] [parent_value] [value]
Insert the node to the tree at the specified [index] with the given [value] under the selected node that has value [parent_value]. We insert starting from the left child of parent, to the right child, if the selected parent already has 2 children then do nothing. If the container at the specified [index] is empty, then ignore [parent_value] and assign the new node as the root of that tree else if the container is not empty and there's no node that has [parent_value] in the tree then do nothing.
Delete [index] [value]
Delete the node of the tree at the specified [index] that contains the given value. Any children of that deleted node will be cut off too from that tree. If the node with the given [value] doesn’t exist on that tree then do nothing.
Print [index] [mode]
Print the tree at the specified [index] depending on the [mode]: pre for preorder, in for inorder, and post for postorder. The format is [Node Value][Space] and at the end print a new line. If it’s empty just print a new line.
Max [index]
Print the maximum value in that tree then a new line. If the tree at [index] is empty, do nothing.
Merge [destination] [from] [value]
Merge 2 different trees, make a new parent node with the given [value], then the left child being the tree at index [destination] and right child being the tree at index [from]. The new parent node now stays at index [destination] while the container at index [from] is now empty.
Disjoint [index] [value]
Find the node with the given [value] at the specified [index] tree, and then make it as a standalone tree. Move this subtree to the first empty index in your chosen data structure (container), if all of them already have a tree stored, then increase the storage size by 1 (meaning now the size of the container may go over the initial size and may goes beyond 10 during the operations) and move it there. If there’s no node that has the given [value] then do nothing. If the node that has the given [value] is the root of that tree, just move the whole tree based on the rule mentioned before. (Hint: First, search the node then cut it off before looking for index that is not full)
Visualization
4 20
Insert 0 10 0 -> Insert 1 11 1 -> Insert 2 12 2 -> Insert 3 13 3 (All of them is root so ignore parent)
Insert 0 0 4 -> Insert 0 0 5 -> Insert 0 0 6 (Node 0 is full so it’s not inserted) -> Insert 0 4 6
Print 0 pre -> Print 0 in -> Print 0 post -> Max 0
0 4 6 5 -> 6 4 0 5 -> 6 4 5 0 -> 6
Merge 0 1 30
Print 0 pre -> Print 0 in -> Print 0 post
30 0 4 6 5 1 -> 6 4 0 5 30 1 -> 6 4 5 0 1 30
Disjoint 0 4 (The subtree is moved to Tree 1 because it’s empty there)
Delete 0 0
Disjoint 1 6 (We extend the container because Tree 0 ~ 3 are already full)
Delete 0 0 (Do nothing because Node 0 doesn’t exist)
Final Output:
Hint
Debug the input
Before trying the problem, you should try out whether your input processing method is correct or not.
Check sample output
You can download the sample output and see the proper format by checking whether there’s space on the end of the line or if there’s a newline.
Do the function in the order it is described
Certain test cases may only test certain functions, so it is recommended to implement the function in the order it is described and try to submit your code after you finish each function (excluding Insert) rather than submitting after you implement all the functions. Only the last test case will test all operations.
Input
In the first line you will be given the initial size of the container [n] and the number of operations we will do [ops].
Followed by [ops] number of lines which will be a series of operations that has been mentioned above.
Limit:
1 <= n <= 10
1 <= ops <= 100
0 <= index, destination, from < n
0 <= value (guaranteed unique), parent_value <= 100
parent will always exist
Output
When we do the operation Print, we output the tree based on the traversal mode specified at the given index. Please note that the format of printing is [Node_val][Space] and then a new line at the end.
When we do the operation Max, we output the highest value in that tree. Please note that the format is just [Max_val] and new line, there's no space after the maximum value.
When the program ends, print all the trees inside the container using inorder traversal with the following format (don’t forget to print a new line after all the nodes are printed):
Tree 0
A B C D E
Tree 1
F G H
…
Tree n-1
X Y Z