In C++

Details and suggestions: Start by implementing a Position class that supports the following operations: left (left child), right child, parent (parent position), isRoot, isLeaf. Implement a BinaryTree class that contains Positions as its nodes.

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.

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.

Procranming excercise. lmplement a method that, diven an input binary tro 7r 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) Procranming excercise. lmplement a method that, diven an input binary tro 7r 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)