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

Subject:Computer SciencePrice:3.87 Bought7

Share With

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