Solution for QID #4056: Beautiful Strawberry Tree 16 Points An inverted ordering tre | StudyHelpMe

Beautiful Strawberry Tree 16 Points An inverted ordering tree is defined as follows: Each node in the tree has either 0, 1, or 2 children (is a binary tree) The tree has a non-null root node containing integer value X All node values in the root's left subtree (if non-empty) have a value greater than X All node values in the root's right subtree (if non-empty) have a value less than X Subtrees of X (if non-empty) are also inverted ordering trees, and thus obey the same ordering property at each node. All values in the tree must be distinct (no duplicate values allowed) . 1 Switcharoo 6 Points Given a valid Inverted ordering tree, design and implement an EFFICIENT algorithm that converts the tree into a valid binary search tree. Pseudocode or Java is fine to describe your algorithm Enter your answer here 2. Give a tight big-O running time bound on the worst case of your algorithm in terms of N, where N is the number of nodes in the original tree. Enter your answer here 3. In 2-3 sentences, explain how you calculated the running time bound above. Enter your answer here