Recall that a binary search tree is a binary tree with keys at each node such that for each node with key k, all keys in the left-sub-tree are less than k and all keys in the right-sub-tree are greater than k (assume all keys are unique). The usual in-order traversal produces a key sequence in non-decreasing order. Write an algorithm (give good pseudocode and a complete analysis) that inverts a binary search tree so that for each node with key k, all keys in the left-sub-tree are greater than k and all nodes in the right-sub-tree are less than k. Thus, an in-order traversal of an inverted tree will produce a key ordering in non-increasing order instead. An example of a binary search tree and its inversion is presented in Figure 2. Your algorithm must be efficient and should not create a new tree.