-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCreateBinaryTree_LikedList.py
More file actions
168 lines (141 loc) · 6.69 KB
/
CreateBinaryTree_LikedList.py
File metadata and controls
168 lines (141 loc) · 6.69 KB
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
import QueueLinkedList as queue
class TreeNode:
def __init__(self, data):
self.data = data
self.leftChild = None
self.rightChild = None
newBt = TreeNode("Drinks")
leftChild = TreeNode("Hot")
tea = TreeNode("Tea")
coffee = TreeNode("coffee")
leftChild.leftChild = tea
leftChild.rightChild = coffee
rightChild = TreeNode("Cold")
newBt.leftChild = leftChild
newBt.rightChild = rightChild
def preOrderTraversal(rootNode): #time: O(n) & space: O(n)
if not rootNode: #-----> O(1)
return
print(rootNode.data) #-----> O(1)
preOrderTraversal(rootNode.leftChild) #------> O(n/2)
preOrderTraversal(rootNode.rightChild) # -----> O(n/2)
def inOrderTraversal(rootNode): #time: O(n) , Space: O(n)
if not rootNode: #-----> O(1)
return
inOrderTraversal(rootNode.leftChild) #------> O(n/2)
print(rootNode.data) #------> O(1)
inOrderTraversal(rootNode.rightChild) #------> O(n/2)
def postOrderTraversal(rootNode): #time: O(n) , Space: O(n)
if not rootNode: #-----> O(1)
return
postOrderTraversal(rootNode.leftChild) #------> O(n/2)
postOrderTraversal(rootNode.rightChild) #------> O(n/2)
print(rootNode.data) #------> O(1)
def levelOrderTraversal(rootNode): #time : O(n) , space = O(n)
if not rootNode: #------> O(1)
return
else:
customQueue = queue.Queue() #------> O(1)
customQueue.enqueue(rootNode) #-----> O(1)
while not(customQueue.isEmpty()): #-----> O(n)
root = customQueue.dequeue() #-----> O(1)
print(root.value.data) #-----> O(1)
if (root.value.leftChild is not None): #----->O(1)
customQueue.enqueue(root.value.leftChild)
if (root.value.rightChild is not None): #------>O(1)
customQueue.enqueue(root.value.rightChild)
def searchBT(rootNode, nodeValue): # time: O(n), space: O(n)
if not rootNode: # O(1)
return
else:
customQueue = queue.Queue() #O(1)
customQueue.enqueue(rootNode) #O(1)
while not(customQueue.isEmpty()): #O(n)
root = customQueue.dequeue() #O(1)
if (root.value.data == nodeValue): #O(1)
return "Success"
if (root.value.leftChild is not None): #O(1)
customQueue.enqueue(root.value.leftChild)
if (root.value.rightChild is not None): #O(1)
customQueue.enqueue(root.value.rightChild)
return "Not found"
def insertNodeBT(rootNode, newNode): #time: O(n), space:O(n)
if not rootNode: #time: O(1)
rootNode = newNode
else:
customQueue = queue.Queue() #time: O(1)
customQueue.enqueue(rootNode) #time: O(1)
while not(customQueue.isEmpty()): #O(n)
root = customQueue.dequeue() #O(1)
if root.value.leftChild is not None: #O(1)
customQueue.enqueue(root.value.leftChild) #O(1)
else:
root.value.leftChild = newNode #O(1)
return "Successfully Inserted"
if root.value.rightChild is not None: #O(1)
customQueue.enqueue(root.value.rightChild) #O(1)
else:
root.value.rightChild = newNode #O(1)
return "Successfully Inserted"
def getDeepestNode(rootNode): #time:O(n) , space:O(n)
if not rootNode:
return
else:
customQueue = queue.Queue()
customQueue.enqueue(rootNode)
while not(customQueue.isEmpty()):
root = customQueue.dequeue()
if (root.value.leftChild is not None):
customQueue.enqueue(root.value.leftChild)
if (root.value.rightChild is not None):
customQueue.enqueue(root.value.rightChild)
deepestNode = root.value
return deepestNode
def deleteDeepestNode(rootNode, dNode):
if not rootNode:
return
else:
customQueue = queue.Queue()
customQueue.enqueue(rootNode)
while not(customQueue.isEmpty()):
root = customQueue.dequeue()
if root.value is dNode:
root.value = None
return
if root.value.rightChild:
if root.value.rightChild is dNode:
root.value.rightChild = None
return
else:
customQueue.enqueue(root.value.rightChild)
if root.value.leftChild:
if root.value.leftChild is dNode:
root.value.leftChild = None
return
else:
customQueue.enqueue(root.value.leftChild)
def deleteNodeBT(rootNode, node): #time: O(n), space:O(n)
if not rootNode: #-----> O(1)
return
else:
customQueue = queue.Queue() #-----> O(1)
customQueue.enqueue(rootNode) #-----> O(1)
while not(customQueue.isEmpty()): #-----> O(n)
root = customQueue.dequeue() #-----> O(1)
if root.value.data == node: #-----> O(1)
dNode = getDeepestNode(rootNode) #-----> O(1)
root.value.data = dNode.data #-----> O(n)
deleteDeepestNode(rootNode, dNode) #-----> O(1)
return "node been successfully deleted" #-----> O(1)
if (root.value.leftChild is not None): #-----> O(1)
customQueue.enqueue(root.value.leftChild) #-----> O(1)
if (root.value.rightChild is not None): #-----> O(1)
customQueue.enqueue(root.value.rightChild) #-----> O(1)
return "Failed"
def deleteEntireBT(rootNode): # time: O(1) , space : O(1)
rootNode.data = None # O(1)
rootNode.leftChild = None # O(1)
rootNode.rightChild = None # O(1)
return "Entire BT deleted"
deleteEntireBT(newBt)
levelOrderTraversal(newBt)