We build up here all the necessary material needed for the exercise.
We also sequentially added up the functions within BST and Node classes on the fly.
import numpy as np
LEFT=0
RIGHT=1
class BST:
count = 0
def __init__(self, elements=()):
self.root = None
self.size = 0
for e in elements:
self.insertion(e)
#self.iterative_insertion(e) # iterative version of insertion
def insertion(self, value):
if self.root == None:
self.root = Node(value)
else:
self.root.insertion(value)
self.size+=1
def iterative_insertion(self,value):
if self.root == None:
self.root = Node(value)
else:
current = self.root
direction = RIGHT if current.value < value else LEFT
while current.children[direction] != None:
current = current.children[direction]
direction = RIGHT if current.value < value else LEFT
current.children[direction] = Node(value)
self.size+=1
def values_between(self,val_min,val_max):
if self.root == None:
return
yield from self.root.values_between(val_min,val_max)
def print_tree(self):
self.root.print_tree()
class Node:
def __init__(self, value, left_child=None, right_child=None): # I add the children in constructor
self.value = value
self.children = [left_child, right_child]
def insertion(self, value):
direction = RIGHT if self.value < value else LEFT
if self.children[direction] == None:
self.children[direction] = Node(value)
else:
self.children[direction].insertion(value)
def values_between(self,val_min,val_max):
if self.value > val_min and self.children[LEFT] != None:
yield from self.children[LEFT].values_between(val_min,val_max)
if val_min < self.value < val_max:
yield self.value
if self.value < val_max and self.children[RIGHT] != None:
yield from self.children[RIGHT].values_between(val_min,val_max)
def print_tree(self, level=0):
print(" |---" * level,self.value)
for child in self.children:
if child == None:
print(" |---" * (level+1),"*")
else:
child.print_tree(level+1)
treeSize = 10
values = np.random.randint(0,100,treeSize)
print("List of values: ",values)
tree = BST(values)
tree.print_tree()
The cost of mirroring a tree is $O(n)$ as:
def mirror_rec(node):
if node == None:
return None
return Node(node.value,mirror_rec(node.children[1]),mirror_rec(node.children[0]))
def mirror(root):
remainder=[root]
while len(remainder)>0:
current=remainder.pop()
# Be careful here that not the 'values' of the children, but the 'pointers' to the children are switched
# so the whole structure of the tree is preserved
current.children=[current.children[1],current.children[0]]
for child in current.children:
remainder.append(child)
treeSize = 10
values = np.random.randint(0,100,treeSize)
print("List of values: ",values)
tree = BST(values)
tree.print_tree()
print("\nMirror rec of the tree: ")
mirror_rec_tree = mirror_rec(tree.root)
mirror_rec_tree.print_tree()
print("\nMirror of the tree: ")
mirror_mirror_rec_tree = mirror_rec(tree.root)
mirror_mirror_rec_tree.print_tree()
# At the tree level
def insertion(self, value):
if self.root == None:
self.root = Node(value)
else:
self.root.insertion(value)
# At the node level (only nodes are recursive, not trees)
def insertion(self, value):
direction = RIGHT if self.value < value else LEFT
if self.children[direction] == None:
self.children[direction] = Node(value)
else:
self.children[direction].insertion(value)
# At the tree level
def iterative_insertion(self,value):
if self.root == None:
self.root = Node(value)
else:
current = self.root
direction = RIGHT if current.value < value else LEFT
while current.children[direction] != None:
current = current.children[direction]
direction = RIGHT if current.value < value else LEFT
current.children[direction] = Node(value)
# At the tree level
def values_between(self,val_min,val_max):
if self.root == None:
return
yield from self.root.values_between(val_min,val_max)
# At the node level
def values_between(self,val_min,val_max):
if self.value > val_min and self.children[LEFT] != None:
yield from self.children[LEFT].values_between(val_min,val_max)
if val_min < self.value < val_max:
yield self.value
if self.value < val_max and self.children[RIGHT] != None:
yield from self.children[RIGHT].values_between(val_min,val_max)
treeSize = 10
values = np.random.randint(0,100,treeSize)
print("List of values: ",values)
tree = BST(values)
tree.print_tree()
print("\nValues between 20 and 80: ",list(tree.root.values_between(20,80)))