Daily_Coding/bst.py at master · dubeamit/Daily_Coding · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
class node:
	def __init__(self, value = None):
		self.value = value
		self.left_child = None
		self.right_child = None
		self.parent = None

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

	def insert(self, value):
		if self.root == None:
			self.root = node(value)
		else:
			self._insert(value, self.root)

	def _insert(self, value, cur_node):
		if value < cur_node.value:
			if cur_node.left_child == None:
				cur_node.left_child = node(value)
				cur_node.left_child.parent = cur_node
			else:
				self._insert(value, cur_node.left_child)

		elif value > cur_node.value:
			if cur_node.right_child == None:
				cur_node.right_child = node(value)
				cur_node.right_child.parent = cur_node
			else:
				self._insert(value, cur_node.right_child)
		else:
			print("Value already in tree")

	def print_tree(self):
		if self.root != None:
			self._print_tree(self.root)

	def _print_tree(self, cur_node):
		if cur_node != None:
			self._print_tree(cur_node.left_child)
			print(str(cur_node.value))
			self._print_tree(cur_node.right_child)

	def height(self):
		if self.root!=None:
			return self._height(self.root,0)
		else:
			return 0

	def _height(self,cur_node,cur_height):
		if cur_node==None: return cur_height
		left_height=self._height(cur_node.left_child,cur_height+1)
		right_height=self._height(cur_node.right_child,cur_height+1)
		return max(left_height,right_height)

	def find(self,value):
		if self.root!=None:
			return self._find(value,self.root)
		else:
			return None

	def _find(self,value,cur_node):
		if value==cur_node.value:
			return cur_node
		elif value<cur_node.value and cur_node.left_child!=None:
			return self._find(value,cur_node.left_child)
		elif value>cur_node.value and cur_node.right_child!=None:
			return self._find(value,cur_node.right_child)

	def search(self,value):
		if self.root!=None:
			return self._search(value,self.root)
		else:
			return False

	def _search(self,value,cur_node):
		if value==cur_node.value:
			return True
		elif value<cur_node.value and cur_node.left_child!=None:
			return self._search(value,cur_node.left_child)
		elif value>cur_node.value and cur_node.right_child!=None:
			return self._search(value,cur_node.right_child)
		return False

	def delete_value(self, value):
	   return self.delete_node(self.find(value))

	def delete_node(self, node):
		# protect against deleting a node not found in the tree
		if node == None or self.find(node.value) == None:
			print('Node to be deleted not found in the tree')
			return None
		# returns the node with min value in tree rooted at input node
		# inorder successor
		def min_value_node(n):
			current = n
			while current.left_child != None:
				current = current.left_child
			return current
		# return the no. of child for a specific node
		def num_childern(n):
			num_childern = 0
			if n.left_child != None:
				num_childern += 1
			if n.right_child != None:
				num_childern += 1
			return num_childern
		# get the parent of node to be deleted
		node_parent = node.parent
		#get the no. of child of node to be deleted
		node_children = num_childern(node)
		# CASE 1(node has no children)
		if node_children == 0:
			if node_parent != None:
				if node_parent.left_child == node:
					node_parent.left_child = None
				else:
					node_parent.right_child = None
			else:
				self.root = None
		# CASE 2(node has a single child)
		if node_children == 1:
			# get the single child node
			if node.left_child != None:
				child = node.left_child
			else:
				child = node.right_child

			if node_parent != None:
				if node_parent.left_child == node:
					node_parent.left_child = child
				else:
					node_parent.right_child = child
			else:
				self.root = child

			child.parent = node_parent

		# CASE 2(node has two children)
		if node_children == 2:
			successor = min_value_node(node.right_child)
			node.value = successor.value
			self.delete_node(successor)

tree = binary_search_tree()
tree.insert(5)
tree.insert(4)
tree.insert(6)
tree.insert(10)
tree.insert(9)
tree.insert(11)
print('Printing tree')
tree.print_tree()
print("deleting 5")
print(tree.delete_value(5))
print('printing tree after deletion')
tree.print_tree()