dosentmatter/tree.py

## tree.py
from collections import deque

class TreeNode:
    def __init__(self, value, children=[]):
        self.value = value
        self.children = children

    def breadth_first_traverse(self):
        breadth_first_queue = deque()
        breadth_first_queue.append(self)
        while breadth_first_queue:
            node = breadth_first_queue.popleft()
            print(node.value)
            for child in node.children:
                if child is not None:
                    breadth_first_queue.append(child)

    def breadth_first_search(self, value):
        breadth_first_queue = deque()
        breadth_first_queue.append(self)
        while breadth_first_queue:
            node = breadth_first_queue.popleft()
            if node.value == value:
                return node
            for child in node.children:
                if child is not None:
                    breadth_first_queue.append(child)

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

    def depth_first_search(self, value):
        if (value == self.value):
            return self
        for child in self.children:
            if child is not None:
                node = child.depth_first_search(value)
                if node is not None:
                    return node
        return None

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

    def _str_helper(self, prefix, tail, newline=True):
        result = ""

        if newline:
            result += "\n"

        self_prefix = (
            type(self).__name__ + 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 = ""

        none_padding = " " * len(type(self).__name__)
        for child in self.children[:-1]:
            if child is None:
                result += type(self)._str_none(none_padding + prefix, False)
            else:
                result += child._str_helper(prefix, False)
        if self.children:
            last_child = self.children[-1]
            if last_child is None:
                result += type(self)._str_none(none_padding + prefix, True)
            else:
                result += self.children[-1]._str_helper(prefix, True)

        return result

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

# old way with extra newline at end
#    def __str__(self):
#        return self._str_helper("", True)
#
#    def _str_helper(self, prefix, tail):
#        result = ""
#
#        self_prefix = (
#            type(self).__name__ + prefix + ("└── " if tail else "├── ")
#        )
#        result += self_prefix + str(self.value) + "\n"
#
#        child_prefix = prefix + ("    " if tail else "|   ")
#
#        none_padding = " " * len(type(self).__name__)
#        for child in self.children[:-1]:
#            if child is None:
#                result += type(self)._str_none(none_padding + child_prefix,
#                                               False)
#            else:
#                result += child._str_helper(child_prefix, False)
#        if self.children:
#            last_child = self.children[-1]
#            if last_child is None:
#                result += type(self)._str_none(none_padding + child_prefix,
#                                               True)
#            else:
#                result += self.children[-1]._str_helper(child_prefix, True)
#
#        return result
#
#    @staticmethod
#    def _str_none(prefix, tail):
#        return prefix + ("└── " if tail else "├── ") + "\n"

class BinaryTreeNode(TreeNode):
    def __init__(self, value, left_child=None, right_child=None):
        super().__init__(value, [left_child, right_child])

    @property
    def left_child(self):
        return self.children[0]

    @left_child.setter
    def left_child(self, value):
        self.children[0] = value

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

    @property
    def right_child(self):
        return self.children[1]

    @right_child.setter
    def right_child(self, value):
        self.children[1] = value

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

    def is_binary_search_tree_node(self, lower_bound=None, upper_bound=None):
        if (
            (lower_bound is not None and self.value <= lower_bound) or
            (upper_bound is not None and upper_bound <= self.value)
        ):
            return False
        if (
            self.has_left_child() and
            not self.left_child.is_binary_search_tree_node(lower_bound,
                                                           self.value)
        ):
            return False
        if (
            self.has_right_child() and
            not self.right_child.is_binary_search_tree_node(self.value,
                                                            upper_bound)
        ):
            return False
        return True

    @classmethod
    def create_from_tree_node(cls, tree_node):
        children = tree_node.children

        left_child = children[0] if len(children) > 0 else None
        if left_child is not None:
            left_child = cls.create_from_tree_node(left_child)

        right_child = children[1] if len(children) > 1 else None
        if right_child is not None:
            right_child = cls.create_from_tree_node(right_child)

        binary_tree_node = cls(tree_node.value, left_child, right_child)
        return binary_tree_node

class BinaryCousinTreeNode(BinaryTreeNode):
    def __init__(self, value, left_child=None, right_child=None,
                 left_cousin=None, right_cousin=None):
        super().__init__(value, left_child, right_child)
        self.left_cousin = left_cousin
        self.right_cousin = right_cousin

    def _str_helper(self, prefix, tail, newline=True):
        result = ""

        if newline:
            result += "\n"

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

        left_cousin = "" if self.left_cousin is None else self.left_cousin.value
        right_cousin = (
            "" if self.right_cousin is None else self.right_cousin.value
        )
        cousins = "({}, {})".format(left_cousin, right_cousin)
        result += cousins

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

        return result

# old way with extra newline at end
#    def _str_helper(self, prefix, tail):
#        result = ""
#
#        self_prefix = (
#            type(self).__name__ + prefix + ("└── " if tail else "├── ")
#        )
#
#        left_cousin = "" if self.left_cousin is None else self.left_cousin.value
#        right_cousin = (
#            "" if self.right_cousin is None else self.right_cousin.value
#        )
#        cousins = "({}, {})".format(left_cousin, right_cousin)
#
#        result += self_prefix + str(self.value) + cousins + "\n"
#
#        child_prefix = prefix + ("    " if tail else "|   ")
#
#        none_padding = " " * len(type(self).__name__)
#        for child in self.children[:-1]:
#            if child is None:
#                result += type(self)._str_none(none_padding + child_prefix,
#                                               False)
#            else:
#                result += child._str_helper(child_prefix, False)
#        if self.children:
#            last_child = self.children[-1]
#            if last_child is None:
#                result += type(self)._str_none(none_padding + child_prefix,
#                                               True)
#            else:
#                result += self.children[-1]._str_helper(child_prefix, True)
#
#        return result

    @classmethod
    def create_from_binary_tree_node(cls, binary_tree_node):
        binary_cousin_tree_node = cls(binary_tree_node.value,
                                      binary_tree_node.left_child,
                                      binary_tree_node.right_child)

        breadth_first_queue = deque()
        breadth_first_queue.append([binary_cousin_tree_node])
        level = 0
        while breadth_first_queue:
            level_nodes = breadth_first_queue.popleft()
            cls.link_cousins(level_nodes)
            next_level_nodes = []
            for node in level_nodes:
                for i, child in enumerate(node.children):
                    if child is not None:
                        binary_cousin_tree_child = cls(child.value,
                                                       child.left_child,
                                                       child.right_child)
                        node.children[i] = binary_cousin_tree_child
                        next_level_nodes.append(binary_cousin_tree_child)
            if next_level_nodes:
                breadth_first_queue.append(next_level_nodes)
            level += 1

        return binary_cousin_tree_node

    @staticmethod
    def link_cousins(nodes):
        if not nodes:
            return
        elif len(nodes) < 2:
            nodes[0].left_cousin = None
            nodes[0].right_cousin = None
        else:
            nodes[0].left_cousin = None
            nodes[0].right_cousin = nodes[1]

            for i, node in enumerate(nodes[1:-1], 1):
                node.left_cousin = nodes[i - 1]
                node.right_cousin = nodes[i + 1]

            nodes[-1].left_cousin = nodes[-2]
            nodes[-1].right_cousin = None

class BinarySearchTreeNode(BinaryTreeNode):
    def put(self, value):
        if value < self.value:
            if self.has_left_child():
                self.left_child.put(value)
            else:
                self.left_child = type(self)(value)
        elif value == self.value:
            return
        else:
            if self.has_right_child():
                self.right_child.put(value)
            else:
                self.right_child = type(self)(value)

    def search(self, value):
        if value < self.value and self.has_left_child():
            node = self.left_child.search(value)
            return node
        elif value == self.value:
            return self
        elif self.has_right_child():
            node = self.right_child.search(value)
            return node
        return None

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

    def breadth_first_traverse(self):
        self.root.breadth_first_traverse()

    def breadth_first_search(self, value):
        return self.root.breadth_first_search(value)

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

    def depth_first_search(self, value):
        return self.root.depth_first_search(value)

    def __str__(self):
        return str(self.root)

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

class BinaryTree(Tree):
    def is_binary_search_tree(self):
        return self.root is None or self.root.is_binary_search_tree_node()

    @classmethod
    def create_from_tree(cls, tree):
        binary_tree = cls()

        root = tree.root
        if root is not None:
            root = BinaryTreeNode.create_from_tree_node(root)
        binary_tree.root = root

        return binary_tree

class BinaryCousinTree(BinaryTree):
    @classmethod
    def create_from_binary_tree(cls, binary_tree):
        binary_cousin_tree = cls()

        root = binary_tree.root
        if root is not None:
            root = BinaryCousinTreeNode.create_from_binary_tree_node(root)
        binary_cousin_tree.root = root

        return binary_cousin_tree

class BinarySearchTree(BinaryTree):
    def put(self, value):
        if self.root:
            self.root.put(value)
        else:
            self.root = BinarySearchTreeNode(value)

    def search(self, value):
        if self.root:
            return self.root.search(value)
        return None

a = TreeNode(5)
b = TreeNode(11)
c = TreeNode(4)
d = TreeNode(2)
e = TreeNode(6, [a, b])
f = TreeNode(9, [c])
g = TreeNode(7, [d, e])
h = TreeNode(5, [None, f])
i = TreeNode(2, [g, h])

tree = Tree.create_from_root(i)

print("Tree")
print(tree)

print()
print("BFT")
tree.breadth_first_traverse()

print()
print("BFS: True, None")
print(tree.breadth_first_search(5) is h)
print(tree.breadth_first_search(-1))

print()
print("DFT")
tree.depth_first_traverse()

print()
print("DFS: True, None")
print(tree.depth_first_search(5) is a)
print(tree.depth_first_search(-1))

binary_tree = BinaryTree.create_from_tree(tree)

print()
print("Tree to BT")
print(binary_tree)

print()
print("Tree to BT is BST: False")
print(binary_tree.is_binary_search_tree())

a = BinarySearchTreeNode(4)
b = BinarySearchTreeNode(7)
c = BinarySearchTreeNode(13)
d = BinarySearchTreeNode(1)
e = BinarySearchTreeNode(6, a, b)
f = BinarySearchTreeNode(14, c)
g = BinarySearchTreeNode(3, d, e)
h = BinarySearchTreeNode(10, None, f)
i = BinarySearchTreeNode(8, g, h)

binary_search_tree = BinarySearchTree.create_from_root(i)

print()
print("BST")
print(binary_search_tree)

print()
print("BST search: True, None")
print(binary_search_tree.search(13) is c)
print(binary_search_tree.search(-1))

print()
print("is BST: True")
print(binary_search_tree.is_binary_search_tree())

binary_search_tree = BinarySearchTree()
binary_search_tree.put(8)
binary_search_tree.put(3)
binary_search_tree.put(10)
binary_search_tree.put(1)
binary_search_tree.put(6)
binary_search_tree.put(14)
binary_search_tree.put(4)
binary_search_tree.put(7)
binary_search_tree.put(13)

print()
print("BST put")
print(binary_search_tree)

print()
print("is BST: True")
print(binary_search_tree.is_binary_search_tree())

binary_search_tree = BinarySearchTree()
binary_search_tree.put('dog')
binary_search_tree.put('cat')
binary_search_tree.put('bear')
binary_search_tree.put('fish')
binary_search_tree.put('turtle')
binary_search_tree.put('cow')
binary_search_tree.put('pig')
binary_search_tree.put('rat')
binary_search_tree.put('lizard')

#          'dog'
#           / \
#      'cat'   'fish'
#       / \        \
# 'bear'   'cow'    'turtle'
#                     /
#                'pig'
#                 / \
#         'lizard'   'rat'

print()
print("BST")
print(binary_search_tree)

print()
print("is BST: True")
print(binary_search_tree.is_binary_search_tree())

binary_cousin_tree = (
    BinaryCousinTree.create_from_binary_tree(binary_search_tree)
)

print()
print("BST to BCT")
print(binary_cousin_tree)

print()
print("BST to BCT is BST: True")
print(binary_cousin_tree.is_binary_search_tree())

def find_prime(n):
    count = 0
    prime = 2
    i = 3
    while count < n:
        if is_prime(i):
            count += 1
            prime = i
        i += 1
    return prime

def find_prime_do_while(n):
    count = None
    prime = None
    i = 0
    while True:
        if is_prime(i):
            if count is None:
                count = 0
            else:
                count += 1
            prime = i
        i += 1
        if count == n:
            return prime

def is_prime(number):
    if (number <= 1):
        return False
    elif (number <= 2):
        return True
    elif number % 2 == 0:
        return False

    i = 3
    while ((i**2) <= number):
        if number % i == 0:
            return False
        i += 2
    return True

print()
print("primes")
print(find_prime(0))
print(find_prime(1))
print(find_prime(2))
print(find_prime(3))
print(find_prime(4))
print(find_prime(5))
print(find_prime(6))

## treetransform.py
'''

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())
	from collections import deque

	class TreeNode:
	def __init__(self, value, children=[]):
	self.value = value
	self.children = children

	def breadth_first_traverse(self):
	breadth_first_queue = deque()
	breadth_first_queue.append(self)
	while breadth_first_queue:
	node = breadth_first_queue.popleft()
	print(node.value)
	for child in node.children:
	if child is not None:
	breadth_first_queue.append(child)

	def breadth_first_search(self, value):
	breadth_first_queue = deque()
	breadth_first_queue.append(self)
	while breadth_first_queue:
	node = breadth_first_queue.popleft()
	if node.value == value:
	return node
	for child in node.children:
	if child is not None:
	breadth_first_queue.append(child)

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

	def depth_first_search(self, value):
	if (value == self.value):
	return self
	for child in self.children:
	if child is not None:
	node = child.depth_first_search(value)
	if node is not None:
	return node
	return None

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

	def _str_helper(self, prefix, tail, newline=True):
	result = ""

	if newline:
	result += "\n"

	self_prefix = (
	type(self).__name__ + 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 = ""

	none_padding = " " * len(type(self).__name__)
	for child in self.children[:-1]:
	if child is None:
	result += type(self)._str_none(none_padding + prefix, False)
	else:
	result += child._str_helper(prefix, False)
	if self.children:
	last_child = self.children[-1]
	if last_child is None:
	result += type(self)._str_none(none_padding + prefix, True)
	else:
	result += self.children[-1]._str_helper(prefix, True)

	return result

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

	# old way with extra newline at end
	# def __str__(self):
	# return self._str_helper("", True)
	#
	# def _str_helper(self, prefix, tail):
	# result = ""
	#
	# self_prefix = (
	# type(self).__name__ + prefix + ("└── " if tail else "├── ")
	# )
	# result += self_prefix + str(self.value) + "\n"
	#
	# child_prefix = prefix + (" " if tail else "\| ")
	#
	# none_padding = " " * len(type(self).__name__)
	# for child in self.children[:-1]:
	# if child is None:
	# result += type(self)._str_none(none_padding + child_prefix,
	# False)
	# else:
	# result += child._str_helper(child_prefix, False)
	# if self.children:
	# last_child = self.children[-1]
	# if last_child is None:
	# result += type(self)._str_none(none_padding + child_prefix,
	# True)
	# else:
	# result += self.children[-1]._str_helper(child_prefix, True)
	#
	# return result
	#
	# @staticmethod
	# def _str_none(prefix, tail):
	# return prefix + ("└── " if tail else "├── ") + "\n"

	class BinaryTreeNode(TreeNode):
	def __init__(self, value, left_child=None, right_child=None):
	super().__init__(value, [left_child, right_child])

	@property
	def left_child(self):
	return self.children[0]

	@left_child.setter
	def left_child(self, value):
	self.children[0] = value

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

	@property
	def right_child(self):
	return self.children[1]

	@right_child.setter
	def right_child(self, value):
	self.children[1] = value

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

	def is_binary_search_tree_node(self, lower_bound=None, upper_bound=None):
	if (
	(lower_bound is not None and self.value <= lower_bound) or
	(upper_bound is not None and upper_bound <= self.value)
	):
	return False
	if (
	self.has_left_child() and
	not self.left_child.is_binary_search_tree_node(lower_bound,
	self.value)
	):
	return False
	if (
	self.has_right_child() and
	not self.right_child.is_binary_search_tree_node(self.value,
	upper_bound)
	):
	return False
	return True

	@classmethod
	def create_from_tree_node(cls, tree_node):
	children = tree_node.children

	left_child = children[0] if len(children) > 0 else None
	if left_child is not None:
	left_child = cls.create_from_tree_node(left_child)

	right_child = children[1] if len(children) > 1 else None
	if right_child is not None:
	right_child = cls.create_from_tree_node(right_child)

	binary_tree_node = cls(tree_node.value, left_child, right_child)
	return binary_tree_node

	class BinaryCousinTreeNode(BinaryTreeNode):
	def __init__(self, value, left_child=None, right_child=None,
	left_cousin=None, right_cousin=None):
	super().__init__(value, left_child, right_child)
	self.left_cousin = left_cousin
	self.right_cousin = right_cousin

	def _str_helper(self, prefix, tail, newline=True):
	result = ""

	if newline:
	result += "\n"

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

	left_cousin = "" if self.left_cousin is None else self.left_cousin.value
	right_cousin = (
	"" if self.right_cousin is None else self.right_cousin.value
	)
	cousins = "({}, {})".format(left_cousin, right_cousin)
	result += cousins

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

	return result

	# old way with extra newline at end
	# def _str_helper(self, prefix, tail):
	# result = ""
	#
	# self_prefix = (
	# type(self).__name__ + prefix + ("└── " if tail else "├── ")
	# )
	#
	# left_cousin = "" if self.left_cousin is None else self.left_cousin.value
	# right_cousin = (
	# "" if self.right_cousin is None else self.right_cousin.value
	# )
	# cousins = "({}, {})".format(left_cousin, right_cousin)
	#
	# result += self_prefix + str(self.value) + cousins + "\n"
	#
	# child_prefix = prefix + (" " if tail else "\| ")
	#
	# none_padding = " " * len(type(self).__name__)
	# for child in self.children[:-1]:
	# if child is None:
	# result += type(self)._str_none(none_padding + child_prefix,
	# False)
	# else:
	# result += child._str_helper(child_prefix, False)
	# if self.children:
	# last_child = self.children[-1]
	# if last_child is None:
	# result += type(self)._str_none(none_padding + child_prefix,
	# True)
	# else:
	# result += self.children[-1]._str_helper(child_prefix, True)
	#
	# return result

	@classmethod
	def create_from_binary_tree_node(cls, binary_tree_node):
	binary_cousin_tree_node = cls(binary_tree_node.value,
	binary_tree_node.left_child,
	binary_tree_node.right_child)

	breadth_first_queue = deque()
	breadth_first_queue.append([binary_cousin_tree_node])
	level = 0
	while breadth_first_queue:
	level_nodes = breadth_first_queue.popleft()
	cls.link_cousins(level_nodes)
	next_level_nodes = []
	for node in level_nodes:
	for i, child in enumerate(node.children):
	if child is not None:
	binary_cousin_tree_child = cls(child.value,
	child.left_child,
	child.right_child)
	node.children[i] = binary_cousin_tree_child
	next_level_nodes.append(binary_cousin_tree_child)
	if next_level_nodes:
	breadth_first_queue.append(next_level_nodes)
	level += 1

	return binary_cousin_tree_node

	@staticmethod
	def link_cousins(nodes):
	if not nodes:
	return
	elif len(nodes) < 2:
	nodes[0].left_cousin = None
	nodes[0].right_cousin = None
	else:
	nodes[0].left_cousin = None
	nodes[0].right_cousin = nodes[1]

	for i, node in enumerate(nodes[1:-1], 1):
	node.left_cousin = nodes[i - 1]
	node.right_cousin = nodes[i + 1]

	nodes[-1].left_cousin = nodes[-2]
	nodes[-1].right_cousin = None

	class BinarySearchTreeNode(BinaryTreeNode):
	def put(self, value):
	if value < self.value:
	if self.has_left_child():
	self.left_child.put(value)
	else:
	self.left_child = type(self)(value)
	elif value == self.value:
	return
	else:
	if self.has_right_child():
	self.right_child.put(value)
	else:
	self.right_child = type(self)(value)

	def search(self, value):
	if value < self.value and self.has_left_child():
	node = self.left_child.search(value)
	return node
	elif value == self.value:
	return self
	elif self.has_right_child():
	node = self.right_child.search(value)
	return node
	return None

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

	def breadth_first_traverse(self):
	self.root.breadth_first_traverse()

	def breadth_first_search(self, value):
	return self.root.breadth_first_search(value)

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

	def depth_first_search(self, value):
	return self.root.depth_first_search(value)

	def __str__(self):
	return str(self.root)

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

	class BinaryTree(Tree):
	def is_binary_search_tree(self):
	return self.root is None or self.root.is_binary_search_tree_node()

	@classmethod
	def create_from_tree(cls, tree):
	binary_tree = cls()

	root = tree.root
	if root is not None:
	root = BinaryTreeNode.create_from_tree_node(root)
	binary_tree.root = root

	return binary_tree

	class BinaryCousinTree(BinaryTree):
	@classmethod
	def create_from_binary_tree(cls, binary_tree):
	binary_cousin_tree = cls()

	root = binary_tree.root
	if root is not None:
	root = BinaryCousinTreeNode.create_from_binary_tree_node(root)
	binary_cousin_tree.root = root

	return binary_cousin_tree

	class BinarySearchTree(BinaryTree):
	def put(self, value):
	if self.root:
	self.root.put(value)
	else:
	self.root = BinarySearchTreeNode(value)

	def search(self, value):
	if self.root:
	return self.root.search(value)
	return None

	a = TreeNode(5)
	b = TreeNode(11)
	c = TreeNode(4)
	d = TreeNode(2)
	e = TreeNode(6, [a, b])
	f = TreeNode(9, [c])
	g = TreeNode(7, [d, e])
	h = TreeNode(5, [None, f])
	i = TreeNode(2, [g, h])

	tree = Tree.create_from_root(i)

	print("Tree")
	print(tree)

	print()
	print("BFT")
	tree.breadth_first_traverse()

	print()
	print("BFS: True, None")
	print(tree.breadth_first_search(5) is h)
	print(tree.breadth_first_search(-1))

	print()
	print("DFT")
	tree.depth_first_traverse()

	print()
	print("DFS: True, None")
	print(tree.depth_first_search(5) is a)
	print(tree.depth_first_search(-1))

	binary_tree = BinaryTree.create_from_tree(tree)

	print()
	print("Tree to BT")
	print(binary_tree)

	print()
	print("Tree to BT is BST: False")
	print(binary_tree.is_binary_search_tree())

	a = BinarySearchTreeNode(4)
	b = BinarySearchTreeNode(7)
	c = BinarySearchTreeNode(13)
	d = BinarySearchTreeNode(1)
	e = BinarySearchTreeNode(6, a, b)
	f = BinarySearchTreeNode(14, c)
	g = BinarySearchTreeNode(3, d, e)
	h = BinarySearchTreeNode(10, None, f)
	i = BinarySearchTreeNode(8, g, h)

	binary_search_tree = BinarySearchTree.create_from_root(i)

	print()
	print("BST")
	print(binary_search_tree)

	print()
	print("BST search: True, None")
	print(binary_search_tree.search(13) is c)
	print(binary_search_tree.search(-1))

	print()
	print("is BST: True")
	print(binary_search_tree.is_binary_search_tree())

	binary_search_tree = BinarySearchTree()
	binary_search_tree.put(8)
	binary_search_tree.put(3)
	binary_search_tree.put(10)
	binary_search_tree.put(1)
	binary_search_tree.put(6)
	binary_search_tree.put(14)
	binary_search_tree.put(4)
	binary_search_tree.put(7)
	binary_search_tree.put(13)

	print()
	print("BST put")
	print(binary_search_tree)

	print()
	print("is BST: True")
	print(binary_search_tree.is_binary_search_tree())

	binary_search_tree = BinarySearchTree()
	binary_search_tree.put('dog')
	binary_search_tree.put('cat')
	binary_search_tree.put('bear')
	binary_search_tree.put('fish')
	binary_search_tree.put('turtle')
	binary_search_tree.put('cow')
	binary_search_tree.put('pig')
	binary_search_tree.put('rat')
	binary_search_tree.put('lizard')

	# 'dog'
	# / \
	# 'cat' 'fish'
	# / \ \
	# 'bear' 'cow' 'turtle'
	# /
	# 'pig'
	# / \
	# 'lizard' 'rat'

	print()
	print("BST")
	print(binary_search_tree)

	print()
	print("is BST: True")
	print(binary_search_tree.is_binary_search_tree())

	binary_cousin_tree = (
	BinaryCousinTree.create_from_binary_tree(binary_search_tree)
	)

	print()
	print("BST to BCT")
	print(binary_cousin_tree)

	print()
	print("BST to BCT is BST: True")
	print(binary_cousin_tree.is_binary_search_tree())

	def find_prime(n):
	count = 0
	prime = 2
	i = 3
	while count < n:
	if is_prime(i):
	count += 1
	prime = i
	i += 1
	return prime

	def find_prime_do_while(n):
	count = None
	prime = None
	i = 0
	while True:
	if is_prime(i):
	if count is None:
	count = 0
	else:
	count += 1
	prime = i
	i += 1
	if count == n:
	return prime

	def is_prime(number):
	if (number <= 1):
	return False
	elif (number <= 2):
	return True
	elif number % 2 == 0:
	return False

	i = 3
	while ((i**2) <= number):
	if number % i == 0:
	return False
	i += 2
	return True

	print()
	print("primes")
	print(find_prime(0))
	print(find_prime(1))
	print(find_prime(2))
	print(find_prime(3))
	print(find_prime(4))
	print(find_prime(5))
	print(find_prime(6))
	'''

	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())