Module 2, Extra exercises
Find below random exercises to practice more with the sorting and the data structures we have seen during the practical lessons. Solutions will be provided in a few days.
Class Definitions (BinaryTree and DiGraphLL)
These classes are provided for the exercises.
[ ]:
# BinaryTree class
class BinaryTree:
def __init__(self, value):
self.__data = value
self.__right = None
self.__left = None
self.__parent = None
def getValue(self):
return self.__data
def setValue(self, newValue):
self.__data = newValue
def getParent(self):
return self.__parent
def setParent(self, tree):
self.__parent = tree
def getRight(self):
return self.__right
def getLeft(self):
return self.__left
def insertRight(self, tree):
if self.__right == None:
self.__right = tree
tree.setParent(self)
def insertLeft(self, tree):
if self.__left == None:
self.__left = tree
tree.setParent(self)
def deleteRight(self):
self.__right = None
def deleteLeft(self):
self.__left = None
def printTree(root):
cur = root
#each element is a node and a depth
#depth is used to format prints (with tabs)
nodes = [(cur,0)]
tabs = ""
lev = 0
while len(nodes) >0:
cur, lev = nodes.pop(-1)
#print("{}{}".format("\t"*lev, cur.getValue()))
if cur.getRight() != None:
print ("{}{} (r)-> {}".format("\t"*lev,
cur.getValue(),
cur.getRight().getValue()))
nodes.append((cur.getRight(), lev+1))
if cur.getLeft() != None:
print ("{}{} (l)-> {}".format("\t"*lev,
cur.getValue(),
cur.getLeft().getValue()))
nodes.append((cur.getLeft(), lev+1))
[ ]:
# Directed graph class
class DiGraphLL:
def __init__(self):
self.nodes = dict()
def insertNode(self, node):
test = self.nodes.get(node, None)
if test == None:
self.nodes[node] = {}
def insertEdge(self, node1, node2, weight):
test = self.nodes.get(node1, None)
test1 = self.nodes.get(node2, None)
if test != None and test1 != None:
test = self.nodes[node1].get(node2, None)
if test != None:
exStr= "Edge {} --> {} already existing.".format(node1,node2)
raise Exception(exStr)
else:
self.nodes[node1][node2] = weight
def __len__(self):
return len(self.nodes)
def nodes(self):
return list(self.nodes.keys())
def graph(self):
return self.nodes
def __str__(self):
ret = ""
for n in self.nodes:
for edge in self.nodes[n]:
ret += "{} -- {} --> {}\n".format(str(n),
str(self.nodes[n][edge]),
str(edge))
return ret
Exercise 1 — Count the Number of Nodes in a Tree
The goal of this exercise is to understand how to traverse a binary tree both recursively and iteratively. You are asked to implement a method in the BinaryTree class that returns the total number of nodes in the subtree rooted at the current node using recursion. Then, implement a second version that computes the same value without using recursion, relying instead on an explicit stack or queue. Both methods should return the same result when tested.
Implement recursive and iterative versions:
def countNodes(self):
pass
def countNodes_iter(self):
pass
Test if you implemented it right with the code below:
[ ]:
# Autograding test for Exercise 1
root = BinaryTree(0)
a = BinaryTree(1); b = BinaryTree(2)
root.insertLeft(a); root.insertRight(b)
try:
assert root.countNodes() == 3
assert root.countNodes_iter() == 3
print('Exercise 1 passed')
except Exception as e:
print('Exercise 1 failed:', e)
Solution
[ ]:
# BinaryTree class
class BinaryTree:
def __init__(self, value):
self.__data = value
self.__right = None
self.__left = None
self.__parent = None
def getValue(self):
return self.__data
def setValue(self, newValue):
self.__data = newValue
def getParent(self):
return self.__parent
def setParent(self, tree):
self.__parent = tree
def getRight(self):
return self.__right
def getLeft(self):
return self.__left
def insertRight(self, tree):
if self.__right == None:
self.__right = tree
tree.setParent(self)
def insertLeft(self, tree):
if self.__left == None:
self.__left = tree
tree.setParent(self)
def deleteRight(self):
self.__right = None
def deleteLeft(self):
self.__left = None
# Recursive and Iterative Solutions for Counting Nodes
def countNodes(self):
count = 1
if self.getLeft() is not None:
count += self.getLeft().countNodes()
if self.getRight() is not None:
count += self.getRight().countNodes()
return count
def countNodes_iter(self):
stack = [self]
count = 0
while stack:
node = stack.pop()
count += 1
if node.getLeft() is not None:
stack.append(node.getLeft())
if node.getRight() is not None:
stack.append(node.getRight())
return count
def printTree(root):
cur = root
#each element is a node and a depth
#depth is used to format prints (with tabs)
nodes = [(cur,0)]
tabs = ""
lev = 0
while len(nodes) >0:
cur, lev = nodes.pop(-1)
#print("{}{}".format("\t"*lev, cur.getValue()))
if cur.getRight() != None:
print ("{}{} (r)-> {}".format("\t"*lev,
cur.getValue(),
cur.getRight().getValue()))
nodes.append((cur.getRight(), lev+1))
if cur.getLeft() != None:
print ("{}{} (l)-> {}".format("\t"*lev,
cur.getValue(),
cur.getLeft().getValue()))
nodes.append((cur.getLeft(), lev+1))
# Autograding test for Exercise 1
root = BinaryTree(0)
a = BinaryTree(1); b = BinaryTree(2)
root.insertLeft(a); root.insertRight(b)
try:
assert root.countNodes() == 3
assert root.countNodes_iter() == 3
print('Exercise 1 passed')
except Exception as e:
print('Exercise 1 failed:', e)
Exercise 1 passed
Exercise 2 — Check Whether a Value Exists in the Tree
This exercise focuses on searching within a binary tree. You should implement a method that returns True if a given value exists anywhere in the tree, using recursion to traverse the nodes. Then, create a second version that performs the same search without recursion, using an explicit stack or queue to explore the tree. Both versions should correctly identify whether the value is present, even if every node needs to be checked.
def contains(self, value):
pass
def contains_iter(self, value):
pass
Test the output with the code below:
[ ]:
root = BinaryTree(1)
a = BinaryTree(2)
b = BinaryTree(3)
root.insertLeft(a)
root.insertRight(b)
print(root.contains(2)) # Expected output: True
print(root.contains_iter(5)) # Expected output: False
Solution
[21]:
# BinaryTree class
class BinaryTree:
def __init__(self, value):
self.__data = value
self.__right = None
self.__left = None
self.__parent = None
def getValue(self):
return self.__data
def setValue(self, newValue):
self.__data = newValue
def getParent(self):
return self.__parent
def setParent(self, tree):
self.__parent = tree
def getRight(self):
return self.__right
def getLeft(self):
return self.__left
def insertRight(self, tree):
if self.__right == None:
self.__right = tree
tree.setParent(self)
def insertLeft(self, tree):
if self.__left == None:
self.__left = tree
tree.setParent(self)
def deleteRight(self):
self.__right = None
def deleteLeft(self):
self.__left = None
# Recursive and Iterative Solutions for Searching a Value
def contains(self, value):
if self.getValue() == value:
return True
if self.getLeft() is not None and self.getLeft().contains(value):
return True
if self.getRight() is not None and self.getRight().contains(value):
return True
return False
def contains_iter(self, value):
stack = [self]
while stack:
node = stack.pop()
if node.getValue() == value:
return True
if node.getLeft() is not None:
stack.append(node.getLeft())
if node.getRight() is not None:
stack.append(node.getRight())
return False
def printTree(root):
cur = root
#each element is a node and a depth
#depth is used to format prints (with tabs)
nodes = [(cur,0)]
tabs = ""
lev = 0
while len(nodes) >0:
cur, lev = nodes.pop(-1)
#print("{}{}".format("\t"*lev, cur.getValue()))
if cur.getRight() != None:
print ("{}{} (r)-> {}".format("\t"*lev,
cur.getValue(),
cur.getRight().getValue()))
nodes.append((cur.getRight(), lev+1))
if cur.getLeft() != None:
print ("{}{} (l)-> {}".format("\t"*lev,
cur.getValue(),
cur.getLeft().getValue()))
nodes.append((cur.getLeft(), lev+1))
root = BinaryTree(1)
a = BinaryTree(2)
b = BinaryTree(3)
root.insertLeft(a)
root.insertRight(b)
print(root.contains(2)) # Expected output: True
print(root.contains_iter(5)) # Expected output: False
True
False
Exercise 3 — Compute the Height of the Tree
Compute the height of a binary tree where a leaf node has height one and an empty subtree has height zero. Implement a recursive method that calculates the height and an iterative method using a stack or queue to track node depth. Both methods should return the same height.
Example: A tree with a root node and two children has height 2. Calling the method on the root node should return 2.
Template for your code:
def height(self):
pass
def height_iter(self):
pass
Example check:
[ ]:
root = BinaryTree(0)
a = BinaryTree(1)
b = BinaryTree(2)
root.insertLeft(a)
root.insertRight(b)
print(root.height()) # Expected output: 2
print(root.height_iter()) # Expected output: 2
Solution
[22]:
# BinaryTree class
class BinaryTree:
def __init__(self, value):
self.__data = value
self.__right = None
self.__left = None
self.__parent = None
def getValue(self):
return self.__data
def setValue(self, newValue):
self.__data = newValue
def getParent(self):
return self.__parent
def setParent(self, tree):
self.__parent = tree
def getRight(self):
return self.__right
def getLeft(self):
return self.__left
def insertRight(self, tree):
if self.__right == None:
self.__right = tree
tree.setParent(self)
def insertLeft(self, tree):
if self.__left == None:
self.__left = tree
tree.setParent(self)
def deleteRight(self):
self.__right = None
def deleteLeft(self):
self.__left = None
# Height (recursive and iterative)
def height(self):
left_h = self.getLeft().height() if self.getLeft() else 0
right_h = self.getRight().height() if self.getRight() else 0
return 1 + max(left_h, right_h)
def height_iter(self):
stack = [(self, 1)]
max_h = 0
while stack:
node, h = stack.pop()
max_h = max(max_h, h)
if node.getLeft() is not None:
stack.append((node.getLeft(), h+1))
if node.getRight() is not None:
stack.append((node.getRight(), h+1))
return max_h
def printTree(root):
cur = root
#each element is a node and a depth
#depth is used to format prints (with tabs)
nodes = [(cur,0)]
tabs = ""
lev = 0
while len(nodes) >0:
cur, lev = nodes.pop(-1)
#print("{}{}".format("\t"*lev, cur.getValue()))
if cur.getRight() != None:
print ("{}{} (r)-> {}".format("\t"*lev,
cur.getValue(),
cur.getRight().getValue()))
nodes.append((cur.getRight(), lev+1))
if cur.getLeft() != None:
print ("{}{} (l)-> {}".format("\t"*lev,
cur.getValue(),
cur.getLeft().getValue()))
nodes.append((cur.getLeft(), lev+1))
root = BinaryTree(0)
a = BinaryTree(1)
b = BinaryTree(2)
root.insertLeft(a)
root.insertRight(b)
print(root.height()) # Expected output: 2
print(root.height_iter()) # Expected output: 2
2
2
Exercise 4.1 — Check if a node has a self edge in a Graph
Consider the DiGraphLL class provided above. Use this code below to generate the following graph:
Code:
[ ]:
G = DiGraphLL()
for i in range(7):
n = "Node_{}".format(i+1)
G.insertNode(n)
G.insertEdge("Node_2", "Node_1", 7)
G.insertEdge("Node_1", "Node_2", 2)
G.insertEdge("Node_1", "Node_4", 5)
G.insertEdge("Node_2", "Node_5", 6)
G.insertEdge("Node_6", "Node_5", 3)
G.insertEdge("Node_4", "Node_5", 15)
G.insertEdge("Node_6", "Node_6", 2)
G.insertEdge("Node_7", "Node_7", 4)
G.insertEdge("Node_4", "Node_4", 4)
print("Size is: {}".format(len(G)))
print("Nodes: {}".format(G.nodes))
Size is: 7
Nodes: {'Node_1': {'Node_2': 2, 'Node_4': 5}, 'Node_2': {'Node_1': 7, 'Node_5': 6}, 'Node_3': {}, 'Node_4': {'Node_5': 15, 'Node_4': 4}, 'Node_5': {}, 'Node_6': {'Node_5': 3, 'Node_6': 2}, 'Node_7': {'Node_7': 4}}
Implement a method called checkSelfEdge() in the DiGraphLL class that takes a node as input and returns True if the node has an edge pointing to itself, and False otherwise. Make sure to first verify that the node exists in the graph.
Hint: Use the adjacency dictionary to determine if the node has an outgoing edge to itself.
def checkSelfEdge(self, node):
pass
[20]:
print("Check for self edge --> \n")
print("Node_10:")
print(G.checkSelfEdge("Node_10")) #should return "node not found"
print("Node_2:")
print(G.checkSelfEdge("Node_2")) #should return False
print("Node_6:")
print(G.checkSelfEdge("Node_6")) #should return True
print("Node_7:")
print(G.checkSelfEdge("Node_7")) #should return True
Check for self edge -->
Node_10:
Node not found
Node_2:
False
Node_6:
True
Node_7:
True
Solution
[24]:
# Directed graph class
class DiGraphLL:
def __init__(self):
self.nodes = dict()
def insertNode(self, node):
test = self.nodes.get(node, None)
if test == None:
self.nodes[node] = {}
def insertEdge(self, node1, node2, weight):
test = self.nodes.get(node1, None)
test1 = self.nodes.get(node2, None)
if test != None and test1 != None:
test = self.nodes[node1].get(node2, None)
if test != None:
exStr= "Edge {} --> {} already existing.".format(node1,node2)
raise Exception(exStr)
else:
self.nodes[node1][node2] = weight
def __len__(self):
return len(self.nodes)
def nodes(self):
return list(self.nodes.keys())
def graph(self):
return self.nodes
def __str__(self):
ret = ""
for n in self.nodes:
for edge in self.nodes[n]:
ret += "{} -- {} --> {}\n".format(str(n),
str(self.nodes[n][edge]),
str(edge))
return ret
def checkSelfEdge(self, node):
test = self.nodes.get(node, None)
if test != None:
subdict = self.nodes[node]
if node in subdict:
return True
else:
return False
else:
return "Node not found"
def isolatedNodes(self):
list_isolated_nodes=[]
for node1 in self.nodes:
subdict1 = self.nodes[node1]
if len(subdict1) > 1:
continue
else:
flag = True
for node2 in self.nodes:
if node1 == node2:
continue
elif node1 in self.nodes[node2]:
flag = False
if flag:
list_isolated_nodes.append(node1)
return list_isolated_nodes
G = DiGraphLL()
for i in range(7):
n = "Node_{}".format(i+1)
G.insertNode(n)
G.insertEdge("Node_2", "Node_1", 7)
G.insertEdge("Node_1", "Node_2", 2)
G.insertEdge("Node_1", "Node_4", 5)
G.insertEdge("Node_2", "Node_5", 6)
G.insertEdge("Node_6", "Node_5", 3)
G.insertEdge("Node_4", "Node_5", 15)
G.insertEdge("Node_6", "Node_6", 2)
G.insertEdge("Node_7", "Node_7", 4)
G.insertEdge("Node_4", "Node_4", 4)
print("Size is: {}".format(len(G)))
print("Nodes: {}".format(G.nodes))
#SOLUTION FOR 4.1
print("\n\n")
print("Check for self edge --> \n")
print("Node_10:")
print(G.checkSelfEdge("Node_10")) #should return "node not found"
print("Node_2:")
print(G.checkSelfEdge("Node_2")) #should return False
print("Node_6:")
print(G.checkSelfEdge("Node_6")) #should return True
print("Node_7:")
print(G.checkSelfEdge("Node_7")) #should return True
#SOLUTION FOR 4.2
print("\n\n")
print("Isolated nodes:\n")
print(G.isolatedNodes())
assert(G.isolatedNodes() == ['Node_3', 'Node_7'])
Size is: 7
Nodes: {'Node_1': {'Node_2': 2, 'Node_4': 5}, 'Node_2': {'Node_1': 7, 'Node_5': 6}, 'Node_3': {}, 'Node_4': {'Node_5': 15, 'Node_4': 4}, 'Node_5': {}, 'Node_6': {'Node_5': 3, 'Node_6': 2}, 'Node_7': {'Node_7': 4}}
Check for self edge -->
Node_10:
Node not found
Node_2:
False
Node_6:
True
Node_7:
True
Isolated nodes:
['Node_3', 'Node_7']
Exercise 4.2 — Check if a node is isolated (no edges with other nodes)
Implement a method called isolatedNodes() in the DiGraphLL class that returns a list of all nodes that are completely isolated from the graph. A node is considered isolated if it has no incoming or outgoing edges to other nodes. Self-loops (edges from the node to itself) should not count as connections: nodes with self-loops are still considered isolated.
def isolatedNodes(self):
pass
Test with:
[ ]:
print("Isolated nodes:\n")
print(G.isolatedNodes())
assert(G.isolatedNodes() == ['Node_3', 'Node_7'])
Solution
See 4.1 solution
Exercise 5
A Binary Search Tree (BST) is a binary tree with the following properties: - The left subtree of a node contains only nodes with values lower than that of the node. - The right subtree of a node contains only nodes with values greater than the node’s. - No duplicate nodes are allowed.
Look at the BST implemented in the code chunck below. Please check carefully how the class is implemented since it might slightly differ from the one you have seen during the practical class. The BST structure created by the script is shown below:
TO DO: We have the BST shown above and a number N. Our task is to find the greatest number (node) in the binary search tree that is less than or equal to N. You are asked to implement the missing method findLargestSmallerKey(self, N)
This method finds the largest key (value of node, as integer) in the BST that is smaller than N. If such a number doesn’t exist, return -1.
TIPS: There are two key parts for the algorithm.
[5]:
class BinarySearchTree:
def __init__(self, value):
self.__data = value
self.__right = None
self.__left = None
self.__parent = None
def getValue(self):
return self.__data
def setValue(self, newValue):
self.__data = newValue
def getParent(self):
return self.__parent
def setParent(self, tree):
self.__parent = tree
def getRight(self):
return self.__right
def getLeft(self):
return self.__left
def insertRight(self, tree):
if self.__right == None:
self.__right = tree
tree.setParent(self)
def insertLeft(self, tree):
if self.__left == None:
self.__left = tree
tree.setParent(self)
# START CODING BELOW HERE:
def findLargestSmallerKey(self, N):
result = -1
while (self != None):
if (self.getValue() < N):
result = self.getValue()
self = self.getRight()
else:
self = self.getLeft()
return result
def createBST(intList):
BST = None
if len(intList) > 0:
BST = BinarySearchTree(intList[0])
for el in intList[1:]:
cur_el = BST
alreadyPresent = False
prev_el = None
while cur_el != None:
prev_el = cur_el
cv = cur_el.getValue()
if cv > el:
cur_el = cur_el.getLeft()
elif cv < el:
cur_el = cur_el.getRight()
else:
alreadyPresent = True
break
if not alreadyPresent:
node = BinarySearchTree(el)
node.setParent(prev_el)
if prev_el.getValue() > el:
prev_el.insertLeft(node)
else:
prev_el.insertRight(node)
return BST
def printTree(root):
cur = root
nodes = [(cur,0)]
tabs = ""
lev = 0
while len(nodes) >0:
cur, lev = nodes.pop(-1)
if cur.getRight() != None:
print ("{}{} (r)-> {}".format("\t"*lev,
cur.getValue(),
cur.getRight().getValue()))
nodes.append((cur.getRight(), lev+1))
if cur.getLeft() != None:
print ("{}{} (l)-> {}".format("\t"*lev,
cur.getValue(),
cur.getLeft().getValue()))
nodes.append((cur.getLeft(), lev+1))
# DO NOT modify code below:
if __name__ == "__main__":
inList = [5,2,1,3,12,9,21,19,25]
BST = createBST(inList)
print("Tree:\n")
printTree(BST)
print("\nGreatest number in the BST that is less than or equal to 24 --> \n")
print(BST.findLargestSmallerKey(24))
print("\nGreatest number in the BST that is less than or equal to 4 --> \n")
print(BST.findLargestSmallerKey(4))
print("\nGreatest number in the BST that is less than or equal to 10 --> \n")
print(BST.findLargestSmallerKey(10))
assert BST.findLargestSmallerKey(24) == 21 , "It should be 21"
assert BST.findLargestSmallerKey(4) == 3, "It should be 3"
assert BST.findLargestSmallerKey( 10) == 9, "It should be 9"
Tree:
5 (r)-> 12
5 (l)-> 2
2 (r)-> 3
2 (l)-> 1
12 (r)-> 21
12 (l)-> 9
21 (r)-> 25
21 (l)-> 19
Greatest number in the BST that is less than or equal to 24 -->
21
Greatest number in the BST that is less than or equal to 4 -->
3
Greatest number in the BST that is less than or equal to 10 -->
9
Excerise 6
Implement the sort() method of the class PancakeSort in the code below.
To test the implementation use the code below, which is equipped with a main code that tests the method by sorting the list [7, 5, 10, -11, 3, -4, 99, 1].
Iterate over the stack of pancakes (list of numbers) starting from the bottom pancake (end of the list) and going towards the top (first pancake). This because at the end of each iteration the biggest pancake (number) will be moved to the bottom of the stack (last position in the list), and we want to reduce the size of the list we work with at each iteration.
At each iteration, identify the biggest pancake (number) and get its position X.
If the biggest pancake is not already at the top, flip the unsorted stack to move it there (in the first position of the list). This means that you must flip the sub-list that goes from 0 to position X.
Now, flip the entire stack (list) so that the biggest pancake is now at the bottom (end of the list).
Repeat the process (step 1 to 3), focusing on a smaller stack each time (excluding the pancake you’ve already sorted, which is now at the end).
Continue until all pancakes are in order (i.e. when you reach the first position in the list)
Keep in mind that with flip we mean to reverse the order of the elements in the list (or sub-list). Below there is an example of how the sorting works:
[ ]:
class SortingAlgorithm:
def __init__(self, data, verbose = True):
self.data = data
self.comparisons = 0
self.operations = 0
self.verbose = verbose
def getData(self):
return self.data
def getOperations(self):
return self.operations
def getComparisons(self):
return self.comparisons
def sort(self):
raise NotImplementedError
class PancakeSort(SortingAlgorithm):
def flip(self, i):
self.data[:i+1] = reversed(self.data[:i+1])
def max_index(self, max_pankcake):
cur_max = 0
for i in range(1,max_pankcake+1):
if self.data[i] > self.data[cur_max]:
cur_max = i
return cur_max
def sort(self):
"""
Implement the Pancake Sort algorithm
"""
n = len(self.data)-1
for big_flip in range(n, 0, -1):
# Find the index of the maximum element in self.data[0..curr_size-1]
mi = self.max_index(big_flip)
# Move the maximum element to end of current self.dataay if it's not already there
# Flip the self.data from 0 to max element index
self.flip(mi)
# Flip the whole self.data
self.flip(big_flip)
return self.data
if __name__ == "__main__":
d = [7, 5, 10, -11 ,3, -4, 99, 1]
print(d)
insSorter = PancakeSort(d)
insSorter.sort()
print(d)
[7, 5, 10, -11, 3, -4, 99, 1]
[-11, -4, 1, 3, 5, 7, 10, 99]