[to understand the context of this problem, you should read the class #08 exercise sheet]

[AED054] Rotating a Tree

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

Base Code

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

The Problem

Add a new method void rightRotate(const T & x) to the class. The function should perform a right rotation 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 BSTree<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