Implement a method that, given an input binary tree T with

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). in C++

Start by implementing a Position class that supports the following methods: left (left child), right (right child), parent (parent position), isRoot, is Leaf (see Lecture 6). Implement a Binary Tree 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. This exercise is easier 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): Start by implementing a Position class that supports the following methods: left (left child), right (right child), parent (parent position), isRoot, is Leaf (see Lecture 6). Implement a Binary Tree 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. This exercise is easier 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)