In C++ please:

1. Programming exercise. Implement a method that, given an input binary tree T witlh n nodes, performs a sequence of up to n rotations (which can be left or right rota- tions) to transform T into a caterpillar (a tree for which every left child is a leaf) (25 pts.) Details and suggestions: Start by implementing a Position class that supports the following methods: left (left child), Tight (right child), parent (parent position), isRoot isLeaf (see Lecture 6) Implement a BinaryTree class that contains Positions as its nodes (see Lecture 6) Implement a Rotation method that takes as input a tree node and a direction (left or right) and outputs the rotated tree ier to do in the linked- list implementation of a binary tree than in an array-based one, but you can decide which one you prefer. You may find it useful to convert T to an intermediate (canonical) form C, for instance, a caterpillar (see Lecture 6 You do not need to worry about any data in your tree, only the structure matters In your main function, demonstrate the process on the trees given in the test cases Bonus: Find the shortest sequence of rotations to transform T into a caterpillar. Test cases (create these trees and demonstrate that your program works on them)