Skip to content

Instantly share code, notes, and snippets.

@dosentmatter

dosentmatter/tree.py

Last active May 4, 2017 03:18
Show Gist options
  • Save dosentmatter/d0f3b7061f7c8410f479229abfc81264 to your computer and use it in GitHub Desktop.
Save dosentmatter/d0f3b7061f7c8410f479229abfc81264 to your computer and use it in GitHub Desktop.
Download ZIP
Random algorithms
Raw
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))
Raw
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())
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment