bst

class Binary_Search_Tree:
	class _BST_Node:
		def __init__(self, value):
			self._value = value
			self._left = None
			self._right = None

	def __init__(self):
		self._root = None
		# self._height = 0

	def insert_element(self, value):
		if self._root is None:
			self._root = self._BST_Node(value)
		else:
			self.insertRecursive(value, self._root)

	def insertRecursive(self, value, node):
		if value < node._value:
			if node._left is None:
				node._left = self._BST_Node(value)
			else:
				node._left = self.insertRecursive(value, node._left);
		if value > node._value:
			if node._right is None:
				node._right = self._BST_Node(value)
			else:
				node._right = self.insertRecursive(value, node._right);
		return node

	def remove_element(self, value):
		if self._root is None:
			return
		self.removeRecursive(value, self._root)

	def removeRecursive(self, value, node):
		print('trying to remove value ' + str(value))
		print(' from subtree rooted at ' + str(node._value))

		if node is None:
			return None

		isRoot = value == self._root._value
		if value == node._value:
			if node._left is None and node._right is None:
				if isRoot:
					self._root = None
				return None
			if node._left is None:
				if isRoot:
					self._root = node._right
				return node._right
			if node._right is None:
				if isRoot:
					self._root = node._left
				return node._left
			else:
				# case of two children

				# in the spirit of recursion, and nothing more...
				swapNode = self.smallestNodeOfSubtree(node._right);

				node._value = swapNode._value
				self.removeRecursive(swapNode._value, node._right);
		if value < node._value:
			node._left = self.removeRecursive(value, node._left);
		if value > node._value:
			node._right = self.removeRecursive(value, node._right);
		return node

	def smallestNodeOfSubtree(self, subtree):
		if subtree._left is None:
			return subtree
		else:
			return self.smallestNodeOfSubtree(subtree._left);

	def in_order(self):
		if self._root is None:
			return '[ ]'
		return '[ ' + self.inOrderRec(self._root)[:-1] + ' ]'
		pass

	def pre_order(self):
		if self._root is None:
			return '[ ]'
		return '[ ' + self.preOrderRec(self._root)[:-1] + ' ]'
		pass

	def post_order(self):
		if self._root is None:
			return '[ ]'
		return '[ ' + self.postOrderRec(self._root)[:-1] + ' ]'
		pass

	# sorry :-1

	def get_height(self):
		pass

	def __str__(self):
		return self.in_order()

	def inOrderRec(self, node):
		string = ''
		if node._left is not None:
			string += self.inOrderRec(node._left)

		string += str(node._value) + ' '

		if node._right is not None:
			string += self.inOrderRec(node._right)
		return string

	def preOrderRec(self, node):
		string = ''
		string += str(node._value) + ' '

		if node._left is not None:
			string += self.preOrderRec(node._left)

		if node._right is not None:
			string += self.preOrderRec(node._right)
		return string

	def postOrderRec(self, node):
		string = ''
		if node._left is not None:
			string += self.postOrderRec(node._left)

		if node._right is not None:
			string += self.postOrderRec(node._right)

		string += str(node._value) + ' '
		return string

	if __name__ == '__main__':
		pass #unit tests make the main section unnecessary.

tree = Binary_Search_Tree();
tree.insert_element(20);
tree.insert_element(10);
tree.insert_element(40);
tree.insert_element(5);
tree.insert_element(12);
tree.insert_element(11);
tree.insert_element(18);
tree.insert_element(19);
tree.insert_element(39);
tree.insert_element(41);
print(tree);
tree.remove_element(12);
print(tree);