Creator: Wassim Marrakchi
Reviewer: Joon Kim
def check(actual, expected):
if expected != actual:
print(f"Function should return the value {expected}, it is returning the value {actual}")
else:
print(f"Congratulations, the test case passed!")
# Decode ascii-encoded hints
def AsciiToText(asci):
result = ""
for i in asci:
result += chr(i)
return result
A queue is a data structure that follows the First-In-First-Out (FIFO) principle.
The main operations of a queue are:
Add(Q,item)
: Add item
to queue Q
.Get(Q)
: Get the item in the queue that was added first, and remove it.def new_queue(n): # n: max no of items
return [None]*n
# TODO: Implement add_queue
def add_queue(Q,item):
# TODO: Implement get_queue
def get_queue(Q):
## Test your implementation
q = new_queue(4)
l = [1,3,2,5]
for i in range(4):
add_queue(q, l[i])
for i in range(4):
item = get_queue(q)
check(item, l[i])
A stack is a data structure that follows the Last-In-First-Out (LIFO) principle.
The main operations of a stack are:
Add(S,item)
: Add item
to the Stack S
Pop(S)
: Get the item in the stack S
that was added last, and remove it.def new_stack(n): # n: max no of items
return [0]+[None]*n
# TODO: Implement add_stack
def add_stack(S,item):
# TODO: Implement pop_stack
def pop_stack(S):
## Test your implementation
q = new_stack(4)
l = [1,3,2,5]
for i in range(4):
add_stack(q, l[i])
for i in range(3,-1,-1):
item = pop_stack(q)
check(item, l[i])
Problem 1
1.1 Write a function that takes in a list of numbers and prints them in reverse order.
# TODO: Complete the function
def revList(L):
# Test your function
check(revList([1,2,3,4]), [4,3,2,1])
check(revList([4,3,2,1]), [1,2,3,4])
check(revList([2,4,6,8,10,12]), [12,10,8,6,4,2])
1.2 Now do the same using a stack
# TODO: Complete the function
def revStack(L):
# Test your function
# Test1
s = revStack([1,2,3,4])
check(s, [4,3,2,1])
# Test2
s = revStack([10,8,6,4,2,0])
check(s, [0,2,4,6,8,10])
Problem 2:
Write a function that reads a string made up of letters and stars (*). Enqueue each letter and dequeue the topmost letter for every star.
So for example, "Jelani***" will become "ani".
# TODO: Complete the function
def letterAndStars(s):
# Test your function
# Test1
q = lettersAndStars("iLoveAddisCoder*")
s1 = "LoveAddisCoder"
s2 = ""
for i in q:
if i != None:
s2 += str(i)
check(s1, s2)
# Test2
q = lettersAndStars("iHate*Lo**v**eShiro")
s1 = "LoveShiro"
s2 = ""
for i in q:
if i != None:
s2 += str(i)
check(s1, s2)
Challenge Problem: (Proposed by Joon Kim)
Given a string of length at most 1000, we say that the string is balanced if it has a left-to-right sequence of characters where every open paranthetical character (i.e.'[', '{', '(') is followed later in the string by a matching enclosing paranthetical character (i.e.']', '}', ')'). A string is unbalanced if it includes any characters besides paranthetical characters. Consider empty strings as balanced.
Examples: "{ [ ] { ( ) } }" is balanced but "[ { } { } ( ]" and "[ m ]" are unbalanced.
# TODO: Implement check_balanced
def check_balanced(par_string):
"""Checks if a string is balanced"""
open_list = ['[', '{', '(']
close_list = [']', '}', ')']
## Test your solution
check(check_balanced("{[]{()}}"), "Balanced")
check(check_balanced("[{}{}(]"), "Unbalanced")
check(check_balanced("]{}([{])}"), "Unbalanced")
check(check_balanced("(k)i"), "Unbalanced")
check(check_balanced(""), "Balanced")
check(check_balanced("()"), "Balanced")
A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child.
The root of a tree is the first node from where the tree originates.
An edge is the connecting link between any two nodes.
A parent of a node is its ancestor.
A child of a node is its descendant.
The depth or level of a node M in the tree is the length of the path from the root of the tree to M.
The height of a tree is one more than the depth of the deepest node in the tree.
All nodes of depth d are at level d in the tree. The root is the only node at level 0, and its depth is 0.
A Binary Search Tree is a node-based binary tree data structure which has the following properties:
Once again, we will use classes to represent our binary tree node structure called "Node". init allows us to initilize the attributes of any node and is run every time we create an object from a class. repr returns the formal representation of the tree.
class Node:
def __init__(self, key):
"""Initialize node attributes."""
self.key = key
self.left = None
self.right = None
def __repr__(self, level = 0):
"""Representation of a tree."""
rep = repr(self.key) + "\n"
if self.left is not None:
rep += "\t" * (level + 1) + "Left:" + self.left.__repr__(level+1)
else:
rep += "\t" * (level + 1) + "(No left child)" + "\n"
if self.right is not None:
rep += "\t" * (level + 1) + "Right:" + self.right.__repr__(level+1)
else:
rep += "\t" * (level + 1) + "(No right child)" + "\n"
return rep
We can now use this class to form our example of a binary search tree as below:
t1_root = Node(8)
t1_root.left = Node(3)
t1_root.left.left = Node(1)
t1_root.left.right = Node(6)
t1_root.left.right.left = Node(4)
t1_root.left.right.right = Node(7)
t1_root.right = Node(10)
t1_root.right.right = Node(14)
t1_root.right.right.left = Node(13)
print(t1_root)
To make sure you understand how this class can be used to form any binary tree, we also reproduced the following tree:
t2_root = Node(2)
t2_root.left = Node(7)
t2_root.right = Node(5)
t2_root.left.left = Node(2)
t2_root.left.right = Node(6)
t2_root.left.right.left = Node(5)
t2_root.left.right.right = Node(11)
t2_root.right.right = Node(9)
t2_root.right.right.left = Node(4)
print(t2_root)
Good! Now, we are ready to implement our operations starting with the insert that takes as input root, the root of a binary search tree, and node, a node we want to add to our binary search tree, and adds key to the binary search tree with root root.
Remember that any binary search tree has to satisfy these three properties:
# TODO: Implement insert
def insert(root, node):
"""Insert key in the root's tree"""
Great! Let's now use insert to reproduce our previous binary search tree:
Note: The order of the insert operations does matter.
# TODO: Reproduce the binary search tree above using insert
BST_root = Node(8)
Now that we have insert, we can move on to implementing a search function to test it!
search takes as input root, the root of a tree, and key, a key we want to search for in the nodes, and returns True if the key is present in the tree and False otherwise.
# TODO: Implement search
def search(root, key):
"""Search for key in the root's tree"""
## Test your implementation of Search and Insert
check(search(t1_root, 7), True)
check(search(t1_root, 12), False)
check(search(Node(2), 3), False)
import copy
ex = copy.deepcopy(t1_root)
check(search(insert(ex, Node(5)), 5), True)
check(search(insert(ex, Node(12)), 12), True)
## Test your new tree
check(repr(BST_root), repr(t1_root))
Awesome! Now all that is left is the delete operation that takes in as input root, the root of a binary search tree and key, a key we want to delete from our binary search tree, and delete key from the binary search tree with root root.
Note 1: You are given minNode, a helper function for delete, that takes as input root, the root of a binary search tree, and returns the minimum key value in the tree. How can you use it to implement delete?
Note 2: Below the following cell are hints to guide you when stuck. Run the cell associated to each hint to read it.
def minNode(root):
"""Return the node with minimum key value in the tree"""
current = root
while(current.left is not None):
current = minNode(root.left)
return current
# TODO: Implement delete
def delete(root, key):
"""Delete key from the root's tree"""
# Run this cell if you want to see Hint 1
print("Hint 1: " + AsciiToText([67,111,110,115,105,100,101,114,32,114,101,99,117,114,115,105,111,110,32,116,111,32,114,101,100,117,99,101,32,116,104,101,32,115,105,122,101,32,111,102,32,116,104,101,32,112,114,111,98,108,101,109,32,97,116,32,101,118,101,114,121,32,114,117,110,32,98,121,32,97,32,115,117,98,116,114,101,101,46,32]))
# Run this cell if you want to see Hint 2
print("Hint 2: " + AsciiToText([87,104,101,110,32,119,101,32,102,105,110,100,32,116,104,101,32,110,111,100,101,32,119,105,116,104,32,116,104,101,32,100,101,115,105,114,101,100,32,107,101,121,32,116,111,32,100,101,108,101,116,101,44,32,116,104,114,101,101,32,112,111,115,115,105,98,105,108,105,116,105,101,115,32,97,114,105,115,101,46]))
# Run this cell if you want to see Hint 3
print("Hint 3: " + AsciiToText([84,104,101,32,116,104,114,101,101,32,112,111,115,115,105,98,105,108,105,116,105,101,115,32,97,114,101,58,32,78,111,100,101,32,116,111,32,98,101,32,100,101,108,101,116,101,100,32,105,115,32,108,101,97,102,59,32,78,111,100,101,32,116,111,32,98,101,32,100,101,108,101,116,101,100,32,104,97,115,32,111,110,108,121,32,111,110,101,32,99,104,105,108,100,59,32,97,110,100,32,78,111,100,101,32,116,111,32,98,101,32,100,101,108,101,116,101,100,32,104,97,115,32,116,119,111,32,99,104,105,108,100,114,101,110,46]))
## Test your implementation
import copy
example1 = Node(2)
insert(example1, Node(3))
check(repr(delete(example1, 3)), repr(Node(2)))
check(repr(delete(example1, 3)), repr(Node(2)))
check(str(repr(delete(example1, 2))), str(None))
insert(example1, Node(4))
insert(example1, Node(5))
insert(example1, Node(3))
insert(example1, Node(7))
insert(example1, Node(8))
insert(example1, Node(9))
p = copy.deepcopy(example1)
insert(example1, Node(1))
insert(example1, Node(0))
delete(example1, 1)
insert(p, Node(0))
check(repr(example1), repr(p))
Congratulations! You have just finished implementing a fully operational Binary Search Tree data structure.
Challenge Problem:
Now that we understand how to represent trees and operate on them, let's consider how we can check if an arbitrary tree with root root is a binary search tree using a function isBST. Keep in mind the following properties of Binary Search Trees:
Note 1: Below the following cells are hints to guide you when stuck. Run the cell associated to each hint to read it.
Note 2: There are at least two solutions to this problem. Any correct solution is a viable solution. Once you find a correct solution, check that it traverses every node only once. If it doesn't but it is correct, you can try to find the more efficient solution ;)
# isBST calls is_Limited_BST to make our task easier
def isBST(root):
"""Returns True if an arbitrary tree is a Binary Search Tree"""
return (is_Limited_BST(root, -float("inf"), +float("inf")))
# TODO: Implement is_Limited_BST
def is_Limited_BST(root, mini, maxi):
"""Returns True if the given tree is a BST and its values are >= mini and <= maxi"""
# Run this cell if you want to see Hint 1
print("Hint 1: " + AsciiToText([69,118,101,114,121,32,112,97,114,101,110,116,39,115,32,107,101,121,32,104,97,115,32,116,111,32,98,101,32,103,114,101,97,116,101,114,32,116,104,97,110,32,105,116,115,32,108,101,102,116,32,99,104,105,108,100,39,115,32,107,101,121,32,97,110,100,32,115,109,97,108,108,101,114,32,116,104,97,110,32,105,116,115,32,114,105,103,104,116,32,99,104,105,108,100,39,115,32,107,101,121,46]))
# Run this cell if you want to see Hint 2
print("Hint 2: " + AsciiToText([109,105,110,78,111,100,101,44,32,100,101,108,101,116,101,39,115,32,104,101,108,112,101,114,32,102,117,110,99,116,105,111,110,44,32,99,97,110,32,98,101,32,117,115,101,100,32,116,111,32,115,111,108,118,101,32,116,104,105,115,32,112,114,111,98,108,101,109,32,116,111,111,46]))
# Run this cell if you want to see Hint 3
print("Hint 3: " + AsciiToText([65,32,104,101,108,112,101,114,32,102,117,110,99,116,105,111,110,32,99,97,110,32,107,101,101,112,32,116,114,97,99,107,32,111,102,32,116,104,101,32,110,97,114,114,111,119,105,110,103,32,109,105,110,32,97,110,100,32,109,97,120,32,97,108,108,111,119,101,100,32,118,97,108,117,101,115,32,97,115,32,111,110,101,32,116,114,97,118,101,114,115,101,115,32,100,111,119,110,32,116,104,101,32,116,114,101,101,46]))
## Test your solution
check(isBST(t1_root), True)
check(isBST(t2_root), False)