Binary Search Tree implementation

BST.py

"""
Defining Binary Search Tree Data Structure 
"""
class Node:
	
	def __init__(self, val, right = None, left = None, parent = None ):
## Inspiration: 
## http://interactivepython.org/runestone/static/pythonds/Trees/SearchTreeImplementation.html
		self.val = val
		self.left = left
		self.right = right
		self.parent = parent

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

	def __repr__(self):
		return repr(self.val)


class BSTree():

	def __init__(self):
		self.root = Node(None)																			

	def _create(self, val):
		## BST representaions are not unique
		## With a given set of numbers, many representations can be drawn.
		if not self.root.val:
			self.root.val = val
		else:
			current = self.root
			stop = False
			while not stop:
				if val < current.val:
					if not current.left:
						current.left = Node(val, parent = current)
						stop = True
					else:
						current = current.left
				elif val > current.val:
					if not current.right:
						current.right = Node(val, parent = current)
						stop = True
					else:
						current = current.right
				else:
					stop = True

	def create_bst(self, arr):
		for val in arr:
			self._create(val)

	def add_value(self, val):
		self._create(val)

	def _delete(self, node):
		parent = node.parent
		if not(node.left and node.right):
			if parent.val < node.val:
				node.val = None
				parent.right = None
			else:
				node.val = None
				parent.left = None
		elif node.left and node.right:
			smallest = node.right
			while smallest.left:
				smallest = smallest.left
			if smallest.parent.val == node.val:
				node.val = smallest.val
				smallest.val = None
				node.right = None
			else:
				node.val = smallest.val
				s_right = smallest.right
				while s_right.right:
					s_right = s_right.right
				s_right.right = node.right
				node.right = smallest.right
				smallest.val = None
				smallest.right = None
		else:
			if node.left:
				child = node.left
			else:
				child = node.right
			if parent.val < node.val:
				node.val = None
				parent.right = child
			else:
				node.val = None
				parent.left = child	


	def _search(self, val):
		current = self.root
		while True:
			if current.val == val:
				return current
			elif current.val > val:
				if current.left:
					current = current.left
				else:
					return False
			else:
				if current.right:
					current = current.right
				else:
					return False

	def delete(self, val):
		## Inspiration :
		## http://www.algolist.net/Data_structures/Binary_search_tree/Removal
		if not self.root.val:
			print("Empty Binary Search Tree! Nothing to delete.")
		else:
			node = self._search(val)
			if not node:
				print("Value not found!")
			else:
				self._delete(node)


def breadth_first_traversal(tree):
	q = [tree.root]
	while len(q):
		current = q.pop(0)
		print(current, end = " ")	## Calls the __str__() method of Node Class
		if current.left:
			q.append(current.left)
		if current.right:
			q.append(current.right)

def dft_pre_order(tree):
	s = [tree.root]
	while len(s):
		current = s.pop()
		print(current, end = " ")	## Calls the __str__() method of Node Class
		if current.right:
			s.append(current.right)
		if current.left:
			s.append(current.left)

def dft_post_order(tree):
	s1 = [tree.root]
	s2 = []
	while len(s1):
		current = s1.pop()
		s2.append(current)
		if current.right:
			s1.append(current.right)
		if current.left:
			s1.append(current.left)
	while len(s2):
		current = s2.pop()
		print(current, end = " ")	## Calls the __str__() method of Node Class


#### Test Cases ####
# arr = [8,3,1,6,4,7,10,14,13]
# tree = BSTree()
# tree.create_bst(arr)
# print("Breadth First Traversal")
# breadth_first_traversal(tree)
# print("\nPre Order Traversal")
# dft_pre_order(tree)
# print("\nPost Order Traversal")
# dft_post_order(tree)
# tree.add_value(5)
# tree.add_value(22)
# print("\n########################")
# print("Breadth First Traversal")
# breadth_first_traversal(tree)
# print("\nPre Order Traversal")
# dft_pre_order(tree)
# print("\nPost Order Traversal")
# dft_post_order(tree)
# tree.delete(5)
# tree.delete(22)
# print("\n########################")
# print("Breadth First Traversal")
# breadth_first_traversal(tree)
# print("\nPre Order Traversal")
# dft_pre_order(tree)
# print("\nPost Order Traversal")
# dft_post_order(tree)
# print()