'''

Question

Given a binary tree T with the following properties:
T is rooted at node r
all right children in T are leaf nodes
there exists a single leaf node, l, which is not a right child
Transform T into T’ such that:
T’ is rooted at node l
All left children in T' are leaf nodes
There exists a single leaf node, r, which is not a left child

Example A: r=Node(1), l=Node(2)

  1                      1                        2
 / \           ->       /            ->          / \
2   3                  2 - 3                    3   1

Example B: r=Node(1), l=Node(5)

      1                    1                   5
     / \                  /                   / \
    2   3                2 - 3               6   4
   /           ->       /            ->           \
  4                    4                           2
 / \                  /                           / \
5   6                5 - 6                       3   1

I shall call this tranformation a rotation.

Meat of solution starts on line 177.

'''

class BinaryTree:
    def __init__(self):
        self.root = None

    def has_root(self):
        return self.root is not None

    def reverse(self):
        if self.has_root():
            self.root.reverse()

    def depth_first_traverse(self):
        if self.has_root():
            self.root.depth_first_traverse()

    def is_symmetric(self):
        if self.has_root():
            return self.root.is_symmetric()
        return True

    def rotate(self):
        if self.has_root():
            self.root = BinaryTreeNode.rotate(self.root)

    def __eq__(self, other):
        if isinstance(other, self.__class__):
            return self.__dict__ == other.__dict__
        return NotImplemented

    def __ne__(self, other):
        if isinstance(other, self.__class__):
            return not self.__eq__(other)
        return NotImplemented

    def __hash__(self):
        return hash(tuple(sorted(self.__dict__.items())))

    def __str__(self):
        if self.has_root():
            return str(self.root)
        return ""

    @classmethod
    def create_from_root(cls, root):
        binary_tree = cls()
        binary_tree.root = root
        return binary_tree

class BinaryTreeNode:
    def __init__(self, value, left_child=None, right_child=None):
        self.value = value
        self.left_child = left_child
        self.right_child = right_child

    def has_left_child(self):
        return self.left_child is not None

    def has_right_child(self):
        return self.right_child is not None

    def reverse(self):
        if self.left_child is not None:
            self.left_child.reverse()
        if self.right_child is not None:
            self.right_child.reverse()

        self.left_child, self.right_child = self.right_child, self.left_child

    def depth_first_traverse(self):
        print(self.value)
        for child in (self.left_child, self.right_child):
            if child is not None:
                child.depth_first_traverse()

    def is_symmetric(self):
        return type(self).are_mirrored(self.left_child, self.right_child)

    def is_mirrored_of(self, other):
        return type(self).are_mirrored(self, other)

    def __eq__(self, other):
        if isinstance(other, self.__class__):
            return self.__dict__ == other.__dict__
        return NotImplemented

    def __ne__(self, other):
        if isinstance(other, self.__class__):
            return not self.__eq__(other)
        return NotImplemented

    def __hash__(self):
        return hash(tuple(sorted(self.__dict__.items())))

    def __str__(self):
        return self._str_helper("", True, False)

    def _str_helper(self, prefix, tail, newline=True):
        result = ""
        
        if newline:
            result += "\n"

        self_prefix = prefix + ("└── " if tail else "├── ") 
        result += self_prefix + str(self.value)

        child_prefix = prefix + ("    " if tail else "|   ") 
        result += self._str_children(child_prefix)

        return result

    def _str_children(self, prefix):
        result = ""

        if self.has_left_child():
            result += self.left_child._str_helper(prefix, False)
        else:
            result += type(self)._str_none(prefix, False)

        if self.has_right_child():
            result += self.right_child._str_helper(prefix, True)
        else:
            result += type(self)._str_none(prefix, True)

        return result

    @staticmethod
    def _str_none(prefix, tail):
        return "\n" + prefix + ("└── " if tail else "├── ")

    @classmethod
    def are_mirrored(cls, node0, node1):
        if node0 is None and node1 is None:
            return True
        if node0 is None or node1 is None:
            return False
        return (
            node0.value == node1.value and
            cls.are_mirrored(node0.left_child, node1.right_child) and
            cls.are_mirrored(node0.right_child, node1.left_child)
        )

    @staticmethod
    def rotate(node):
        parent = None
        right_sibling = None

        current_node = node

        while current_node is not None:
            next_node = current_node.left_child
            next_right_sibling = current_node.right_child

            current_node.left_child = right_sibling
            current_node.right_child = parent

            parent = current_node
            right_sibling = next_right_sibling

            current_node = next_node

        node = parent
        return node
    
# Tests

btn = BinaryTreeNode

a = BinaryTree.create_from_root(btn(1, btn(2), btn(3)))
print("a:")
print(a)
a.rotate()
print("a rotated:")
print(a)

b = BinaryTree.create_from_root(btn(1, btn(2, btn(4, btn(5), btn(6))), btn(3)))
print("b:")
print(b)
b.rotate()
print("b rotated:")
print(b)

c = BinaryTree.create_from_root(btn(1, btn(2, btn(4, btn(5), btn(6))), btn(3)))
d = BinaryTree.create_from_root(btn(1, btn(2, btn(4, btn(5), btn(6))), btn(3)))
print("c:")
print(c)
print("d:")
print(d)
print("c == d:")
print(c == d)

e = BinaryTree.create_from_root(btn(1, btn(2, btn(3, btn(5), btn(6)), btn(4, btn(7), btn(8))), btn(2, btn(4, btn(8), btn(7)), btn(3, btn(6), btn(5)))))
print("e:")
print(e)
print("e is symmetric:")
print(e.is_symmetric())