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

Answer:

(1)

In the given problem, the Inverted ordering tree is defined as an ordered binary tree that is inverted or is a mirror image of a binary tree.

For instance.

For a valid binary tree, all the values in the left subtree should be less than the root node and all the values in the right subtree should be greater than the root node.

When this implementation of a binary tree is inverted meaning values in left subtree > root node and values in right subtree < root node we get an inverted ordering tree.

Now the question of what are the ways we can convert a given inverted ordering tree into a valid binary tree.

One can fancy a very simple recursive algorithm that does the work.

What we can do is, traverse the inverted ordering tree from the root node all the way to the terminal leaf nodes and at every node N, we swap its left and right child.

For example, for a root Node say N, it has a left child L and right child R, so for every node N, we will swap L and R and repeat the process until Tree = Null.

This algorithm can be implemented by many data structures like LIFO stack and FIFO queue. For example, for every node in the stack, we first pop the node from the stack, push the left child of the popped node into another stack S1 and push the right child of the popped node into another stack S2 and just repeat the process.

PSEUDO CODE:

function invertTree(Node N) {

        if (N  != null)  {

             temp = left;

             left = right;

             right = temp;

            //recursive call

             invertTree(N -> left);
             
             invertTree(N -> right);  
       }

       else {
              print("the tree is empty")

       }
}

(2)

The worst-case time complexity for this algorithm if N is the number of nodes in the tree is O(n) or big-O(n).

(3)

Since the total number of nodes in the tree are N, the algorithm will take O(n) time to traverse through all the N nodes, so the worst-case time complexity is O(n)