-
Notifications
You must be signed in to change notification settings - Fork 1
/
BINARY_TREE_CREATION.PY
205 lines (186 loc) · 6.73 KB
/
BINARY_TREE_CREATION.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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
class Node:
def __init__(self,data):
self.data=data
self.left=None
self.right=None
# This class represent node and state
class State:
def __init__(self,node,state):
self.node = node
self.state= state
# In this class there is basics of tree like creation of tree and height , size ,total nodes etc.
class Tree:
# print tree in some good manner
def print_tree(self,tree):
if tree:
if tree.left and tree.right:
print(f" {tree.data}")
print(f" |")
print(f"{tree.left.data}<-->{tree.right.data}")
elif tree.left and not tree.right:
print(f" {tree.data}")
print(f" |")
print(f"{tree.left.data}<-->None")
elif tree.right and not tree.left:
print(f" {tree.data}")
print(f" |")
print(f"None<-->{tree.right.data}")
self.print_tree(tree.left)
self.print_tree(tree.right)
# get total node from left and return to right and calculate total nodes
def Method_1_no_of_node(self,tree,Total_node):
if tree:
Total_node = self.Method_1_no_of_node(tree.left,Total_node+1)
Total_node = self.Method_1_no_of_node(tree.right,Total_node)
return Total_node
return Total_node
# get nodes from left
# get nodes from right
# add 1 and return
def Method_2_no_of_node(self,tree):
if tree:
left_node_size = self.Method_2_no_of_node(tree.left)
right_node_size = self.Method_2_no_of_node(tree.right)
return left_node_size+right_node_size+1
return 0
# get height of left
# get height of right
# get maximum outof return (left,right)+1
def Method_1_get_height(self,tree):
if tree:
return 1+max(self.Method_1_get_height(tree.left),self.Method_1_get_height(tree.right))
return 0
def Method_2_get_height(self,tree):
if tree:
left_height = self.Method_2_get_height(tree.left)
right_height = self.Method_2_get_height(tree.right)
return max(left_height,right_height)+1
return 0
# travel all nodes and all it's value and return it
def Method_1_total_sum(self,tree,total_sum):
if tree:
total_sum = self.Method_1_total_sum(tree.left,total_sum+tree.data)
total_sum = self.Method_1_total_sum(tree.right,total_sum)
return total_sum
return total_sum
def Method_2_total_sum(self,tree):
if tree:
left_sum = self.Method_2_total_sum(tree.left)
right_sum = self.Method_2_total_sum(tree.right)
total_sum = left_sum+right_sum+tree.data
return total_sum
return 0
# travel all nodes and return maximum out of it
def Method_1_max_node(self,tree,max_node):
if tree:
max_node = max(tree.data,max_node)
max_node = self.Method_1_max_node(tree.left,max_node)
max_node = self.Method_1_max_node(tree.right,max_node)
return max_node
return max_node
# first find max out of left
# then find max out of right
# return maximum out of both left and right
def Method_2_max_node(self,tree):
if tree:
left_max = self.Method_2_max_node(tree.left)
right_max = self.Method_2_max_node(tree.right)
return max(left_max,right_max,tree.data)
return -9999999
# In this class there is different methods of traversal iterative ,recursive and level order
class Traversal:
# left
# print
# right
def recursive_in_order(self,tree):
if tree:
self.recursive_in_order(tree.left)
print(tree.data)
self.recursive_in_order(tree.right)
# print
# left
# right
def recursive_pre_order(self,tree):
if tree:
print(tree.data)
self.recursive_pre_order(tree.left)
self.recursive_pre_order(tree.right)
# left
# right
# print
def recursive_post_order(self,tree):
if tree:
self.recursive_post_order(tree.left)
self.recursive_post_order(tree.right)
print(tree.data)
# will use queue here
# remove
# print
# add
# remove element from queue print the element and add it's childrens
def level_order(self,tree):
queue = []
queue.append(tree)
while queue:
size = len(queue)
for i in range(size):
node = queue.pop(0)
print(node.data,end="-")
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
print()
# tree creation function
def build_tree(arr):
stack = []
root = Node(arr[0])
stack.append(State(root,1))
# if none then increase
# if state = 3 pop
# else increment state of top make new node connect then push
i=0
while stack:
top = stack[-1]
if top.state==1:
i+=1
if arr[i]!=None:
nn = Node(arr[i])
top.node.left = nn
stack.append(State(top.node.left,1))
else:
top.node.left=None
top.state+=1
elif top.state==2:
i+=1
if arr[i]!=None:
nn = Node(arr[i])
top.node.right= nn
stack.append(State(top.node.right,1))
else:
top.node.right=None
top.state+=1
else:
stack.pop()
return root
if __name__ == '__main__':
arr = [50,25,12,None,None,37,30,None,None,None,75,62,None,70,None,None,87,None,None]
tree = build_tree(arr)
obj = Tree()
# obj.print_tree(tree)
traversal = Traversal()
# print(obj.Method_1_get_height(tree))
# print(obj.Method_2_get_height(tree))
# print(obj.Method_1_no_of_node(tree,0))
# print(obj.Method_2_no_of_node(tree))
# print(obj.Method_1_total_sum(tree,0))
# print(obj.Method_2_total_sum(tree))
# print(obj.Method_1_max_node(tree,-999999))
# print(obj.Method_2_max_node(tree))
# traversal.recursive_in_order(tree)
# traversal.iterative_in_order(tree)
# traversal.recursive_pre_order(tree)
# traversal.iterative_pre_order(tree)
# traversal.recursive_post_order(tree)
# traversal.iterative_post_order(tree)
# traversal.level_order(tree)