-
Notifications
You must be signed in to change notification settings - Fork 0
/
binaryTreeLinkedList.py
168 lines (134 loc) · 4.92 KB
/
binaryTreeLinkedList.py
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
159
160
161
162
163
# Binary Tree implementation using Linked List
# Create Traverse Search Insert Delete
# Binary tree has always at most 2 children
# this module could be found in the Stack-Queue repo
import queueLinkedList as queue
class TreeNode:
def __init__(self, data):
self.data = data #value
self.left_child = None
self.righ_child = None
def preOrderTraversal(root_node):
if not root_node:
return
print(root_node.data)
preOrderTraversal(root_node.left_child)
preOrderTraversal(root_node.right_child)
def inOrderTraversal(root_node):
if not root_node:
return
inOrderTraversal(root_node.left_child)
print(root_node.data)
inOrderTraversal(root_node.right_child)
def postOrderTraversal(root_node):
if not root_node:
return
postOrderTraversal(root_node.left_child)
postOrderTraversal(root_node.right_child)
print(root_node.data)
def levelOrderTraversal(root_node):
if not root_node:
return
else:
customQueue = queue.Queue()
customQueue.enqueue(root_node)
while not(customQueue.isEmpty()):
root = customQueue.dequeue()
print(root.value.data)
if (root.value.left_child is not None):
customQueue.enqueue(root.value.left_child)
if (root.value.right_child is not None):
customQueue.enqueue(root.value.right_child)
def searchBT(root_node, nodeValue):
if not root_node:
return "Binary Tree does not exist"
else:
customQueue = queue.Queue()
customQueue.enqueue(root_node)
while not(customQueue.isEmpty()):
root = customQueue.dequeue()
if root.value.data == nodeValue:
return "Success"
if (root.value.left_child is not None):
customQueue.enqueue(root.value.left_child)
if (root.value.right_child is not None):
customQueue.enqueue(root.value.right_child)
return "Not Found"
def insertNodeBT(root_node, newNode):
if not root_node:
root_node = newNode
else:
customQueue = queue.Queue()
customQueue.enqueue(root_node)
while not(customQueue.isEmpty()):
root = customQueue.dequeue()
if root.value.left_child is not None:
customQueue.enqueue(root.value.left_child)
else:
root.value.left_child = newNode
return "Inserted"
if root.value.right_child is not None:
customQueue.enqueue(root.value.right_child)
else:
root.value.right_child = newNode
return "Inserted"
def getDeepestNode(root_node):
if not root_node:
return
else:
customQueue = queue.Queue()
customQueue.enqueue(root_node)
while not(customQueue.isEmpty()):
root = customQueue.dequeue()
if (root.value.left_child is not None):
customQueue.enqueue(root.value.left_child)
if (root.value.right_child is not None):
customQueue.enqueue(root.value.right_child)
deepestNode = root.value
return deepestNode
def deleteDeepestNode(root_node, dNode):
if not root_node:
return
else:
customQueue = queue.Queue()
customQueue.enqueue(root_node)
while not(customQueue.isEmpty()):
root = customQueue.dequeue()
if root.value is dNode:
root.value = None
return
if root.value.right_child:
if root.value.right_child is dNode:
root.value.right_child = None
return
else:
customQueue.enqueue(root.value.right_child)
if root.value.left_child:
if root.value.left_child is dNode:
root.value.left_child = None
return
else:
customQueue.enqueue(root.value.left_child)
def deleteNodeBT(root_node, node):
if not root_node:
return "Binary Tree does not exist"
else:
customQueue = queue.Queue()
customQueue.enqueue(root_node)
while not(customQueue.isEmpty()):
root = customQueue.dequeue()
if root.value.data == node:
dNode = getDeepestNode(root_node)
root.value.data = dNode.data
deleteDeepestNode(root_node, dNode)
return "Deleted"
if (root.value.left_child is not None):
customQueue.enqueue(root.value.left_child)
if (root.value.right_child is not None):
customQueue.enqueue(root.value.right_child)
return "Failed to delete"
def deleteBT(root_node):
root_node.data = None
root_node.left_child = None
root_node.right_child = None
return "Deleted"