In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of December 7th
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #08 exercise sheet]

[AED047] Rotating a Tree

In this problem you should only submit a binarySearchTree.h file with a self-containing definition of a class BinarySearchTree<T>

Base Code

Use as a basis the class BinarySearchTree<T> (see code | download code) which implements a generic binary search tree that was given in the classes, with methods to read insert, remove and check of a value exists, to write a preOrder traversal with N as null nodes and the number of nodes and height of the tree.

The Problem

Add a new method void rightRotate(const T & x) to the class. The function should right rotate the tree on at the node with value x as shown in the figure below. If the rotation is not possible (the element does not exist or has no left child) the function should do nothing.

You can be assured that there will be no repeated values in the tree.

Submission

You should submit the file binarySearchTree.h with the method rightRotate added to binarySearchTree<T> as requested (and without removing any of the other existing methods). You can however create additional methods, if you need them.

Mooshak will use the following code to link to your class, read the inputs, build the trees and call your method, printing its result.

#include <iostream>
#include <string>

#include "binarySearchTree.h"

int main() {
  BSTree<int> t;

  // Read tree by inserting numbers
  int n;
  std::cin >> n;
  for (int i=0; i<n; i++) {
    int x;
    std::cin >> x;
    t.insert(x);
  }

  // Read rotation asked and print before and after tree
  int x;
  std::cin >> x;
  t.printPreOrder();
  t.rightRotate(x);
  std::cout << "rightRotate(" << x << ")" << std::endl;
  t.printPreOrder();
  
  return 0;
}

6
42 23 56 10 30 8
42

preOrder: 42 23 10 8 N N N 30 N N 56 N N
rightRotate(42)
preOrder: 23 10 8 N N N 42 30 N N 56 N N

Explanation of Example Input 1

6
42 23 56 10 30 8
23

preOrder: 42 23 10 8 N N N 30 N N 56 N N
rightRotate(23)
preOrder: 42 10 8 N N 23 N 30 N N 56 N N

6
42 23 56 10 30 8
30

preOrder: 42 23 10 8 N N N 30 N N 56 N N
rightRotate(30)
preOrder: 42 23 10 8 N N N 30 N N 56 N N