+1 (208) 254-6996 [email protected]
  

Please following the requirement which is in the PDF file(cs261 assignment instruction), and give the same output as the PDF file shows. 

Then, answer the 4 questions which I give in word file and I also provide the pdf files which the questions required.

Don't use plagiarized sources. Get Your Custom Essay on
Data Structure (Python)
Just from $13/Page
Order Essay

In addition to the programming portion of the assignment, you will also be answering some questions about binary search trees. Some of the questions will require you to write your answers on the tree in empty_graph.pdf Preview the document. We will assume that any empty node boxes are non-existent nodes. For each of these problems, print out a copy of the blank tree, fill in the answers for the question, and please make sure to write the question number and your name on the sheet. If you know how to annotate PDF files directly, you can also do that instead of printing off the trees (this may be easier since you will have to submit a digital version of your solutions).

Question 1

Show the binary search tree built by adding numbers in this specific order, assuming the graph is empty to start with:  3, 63,  2, 89, 16, 24, 19, 30, 52, 24, 9, 4, 40 (You may need to add more boxes to the diagram).

Question 2

The trouble with binary search trees is that they can become unbalanced depending on the order that you insert values. Give an order for inserting the letters   I, P, A, F, W, Q, X, E,  G, N, S, B, Z such that the resulting tree is a complete binary search tree. Please make that your intermediate trees are also complete binary search trees as well. (Hint: it might be helpful to first draw the full/complete tree to figure out how the values must be arranged, then you can determine the order to add them.)

Question 3

· Part A: Given the following tree, Question3.pdf Preview the document, show the tree after removing the value 38.

· Part B: Using the tree produced by Part A, show the tree after removing the value 17.

Question 4

The computer has built the following decision tree for the Guess the Animal Game, Question4.pdf Preview the document. The player has an animal in mind and will answer the questions shown in the tree. Each of the player’s responses is used to determine the next question to ask. For example, if the player is thinking of a sea turtle, she would answer Yes to the first (top) question, “does it live in the water?”, which leads to the second question “is it a mammal?”, to which she would answer No.

Show the decision tree that the computer should build after adding a Zergling and a question to differentiate it, “Does it eat space marines?”, to the tree. The question and the animal should be added below existing questions in the tree. Note that Zerglings do eat space marines, do not live in the water, do not climb trees. 

# Course: CS261 – Data Structures # Student Name: # Assignment: # Description: class Stack: “”” Class implementing STACK ADT. Supported methods are: push, pop, top, is_empty DO NOT CHANGE THIS CLASS IN ANY WAY YOU ARE ALLOWED TO CREATE AND USE OBJECTS OF THIS CLASS IN YOUR SOLUTION “”” def __init__(self): “”” Initialize empty stack based on Python list “”” self._data = [] def push(self, value: object) -> None: “”” Add new element on top of the stack “”” self._data.append(value) def pop(self) -> object: “”” Remove element from top of the stack and return its value “”” return self._data.pop() def top(self) -> object: “”” Return value of top element without removing from stack “”” return self._data[-1] def is_empty(self): “”” Return True if the stack is empty, return False otherwise “”” return len(self._data) == 0 def __str__(self): “”” Return content of the stack as a string (for use with print) “”” data_str = [str(i) for i in self._data] return “STACK: { ” + “, “.join(data_str) + ” }” class Queue: “”” Class implementing QUEUE ADT. Supported methods are: enqueue, dequeue, is_empty DO NOT CHANGE THIS CLASS IN ANY WAY YOU ARE ALLOWED TO CREATE AND USE OBJECTS OF THIS CLASS IN YOUR SOLUTION “”” def __init__(self): “”” Initialize empty queue based on Python list “”” self._data = [] def enqueue(self, value: object) -> None: “”” Add new element to the end of the queue “”” self._data.append(value) def dequeue(self) -> object: “”” Remove element from the beginning of the queue and return its value “”” return self._data.pop(0) def is_empty(self): “”” Return True if the queue is empty, return False otherwise “”” return len(self._data) == 0 def __str__(self): “”” Return content of the stack as a string (for use with print) “”” data_str = [str(i) for i in self._data] return “QUEUE { ” + “, “.join(data_str) + ” }” class TreeNode: “”” Binary Search Tree Node class DO NOT CHANGE THIS CLASS IN ANY WAY “”” def __init__(self, value: object) -> None: “”” Init new Binary Search Tree DO NOT CHANGE THIS METHOD IN ANY WAY “”” self.value = value # to store node’s data self.left = None # pointer to root of left subtree self.right = None # pointer to root of right subtree def __str__(self): return str(self.value) class BST: def __init__(self, start_tree=None) -> None: “”” Init new Binary Search Tree DO NOT CHANGE THIS METHOD IN ANY WAY “”” self.root = None # populate BST with initial values (if provided) # before using this feature, implement add() method if start_tree is not None: for value in start_tree: self.add(value) def __str__(self) -> str: “”” Return content of BST in human-readable form using in-order traversal DO NOT CHANGE THIS METHOD IN ANY WAY “”” values = [] self._str_helper(self.root, values) return “TREE in order { ” + “, “.join(values) + ” }” def _str_helper(self, cur, values): “”” Helper method for __str__. Does in-order tree traversal DO NOT CHANGE THIS METHOD IN ANY WAY “”” # base case if cur is None: return # recursive case for left subtree self._str_helper(cur.left, values) # store value of current node values.append(str(cur.value)) # recursive case for right subtree self._str_helper(cur.right, values) # —————————————————————— # def add(self, value: object) -> None: “”” TODO: Write this implementation “”” pass def contains(self, value: object) -> bool: “”” TODO: Write this implementation “”” return True def get_first(self) -> object: “”” TODO: Write this implementation “”” return None def remove_first(self) -> bool: “”” TODO: Write this implementation “”” return True def remove(self, value) -> bool: “”” TODO: Write this implementation “”” return True def pre_order_traversal(self) -> Queue: “”” TODO: Write this implementation “”” return Queue() def in_order_traversal(self) -> Queue: “”” TODO: Write this implementation “”” return Queue() def post_order_traversal(self) -> Queue: “”” TODO: Write this implementation “”” return Queue() def by_level_traversal(self) -> Queue: “”” TODO: Write this implementation “”” return Queue() def is_full(self) -> bool: “”” TODO: Write this implementation “”” return True def is_complete(self) -> bool: “”” TODO: Write this implementation “”” return True def is_perfect(self) -> bool: “”” TODO: Write this implementation “”” return True def size(self) -> int: “”” TODO: Write this implementation “”” return 0 def height(self) -> int: “”” TODO: Write this implementation “”” return -1 def count_leaves(self) -> int: “”” TODO: Write this implementation “”” return 0 def count_unique(self) -> int: “”” TODO: Write this implementation “”” return 0 # BASIC TESTING – PDF EXAMPLES if __name__ == ‘__main__’: “”” add() example #1 “”” print(“\nPDF – method add() example 1”) print(“—————————-“) tree = BST() print(tree) tree.add(10) tree.add(15) tree.add(5) print(tree) tree.add(15) tree.add(15) print(tree) tree.add(5) print(tree) “”” add() example 2 “”” print(“\nPDF – method add() example 2”) print(“—————————-“) tree = BST() tree.add(10) tree.add(10) print(tree) tree.add(-1) print(tree) tree.add(5) print(tree) tree.add(-1) print(tree) “”” contains() example 1 “”” print(“\nPDF – method contains() example 1”) print(“———————————“) tree = BST([10, 5, 15]) print(tree.contains(15)) print(tree.contains(-10)) print(tree.contains(15)) “”” contains() example 2 “”” print(“\nPDF – method contains() example 2”) print(“———————————“) tree = BST() print(tree.contains(0)) “”” get_first() example 1 “”” print(“\nPDF – method get_first() example 1”) print(“———————————-“) tree = BST() print(tree.get_first()) tree.add(10) tree.add(15) tree.add(5) print(tree.get_first()) print(tree) “”” remove() example 1 “”” print(“\nPDF – method remove() example 1”) print(“——————————-“) tree = BST([10, 5, 15]) print(tree.remove(7)) print(tree.remove(15)) print(tree.remove(15)) “”” remove() example 2 “”” print(“\nPDF – method remove() example 2”) print(“——————————-“) tree = BST([10, 20, 5, 15, 17, 7, 12]) print(tree.remove(20)) print(tree) “”” remove() example 3 “”” print(“\nPDF – method remove() example 3”) print(“——————————-“) tree = BST([10, 5, 20, 18, 12, 7, 27, 22, 18, 24, 22, 30]) print(tree.remove(20)) print(tree) # comment out the following lines # if you have not yet implemented traversal methods print(tree.pre_order_traversal()) print(tree.in_order_traversal()) print(tree.post_order_traversal()) print(tree.by_level_traversal()) “”” remove_first() example 1 “”” print(“\nPDF – method remove_first() example 1”) print(“————————————-“) tree = BST([10, 15, 5]) print(tree.remove_first()) print(tree) “”” remove_first() example 2 “”” print(“\nPDF – method remove_first() example 2”) print(“————————————-“) tree = BST([10, 20, 5, 15, 17, 7]) print(tree.remove_first()) print(tree) “”” remove_first() example 3 “”” print(“\nPDF – method remove_first() example 3”) print(“————————————-“) tree = BST([10, 10, -1, 5, -1]) print(tree.remove_first(), tree) print(tree.remove_first(), tree) print(tree.remove_first(), tree) print(tree.remove_first(), tree) print(tree.remove_first(), tree) print(tree.remove_first(), tree) “”” Traversal methods example 1 “”” print(“\nPDF – traversal methods example 1”) print(“———————————“) tree = BST([10, 20, 5, 15, 17, 7, 12]) print(tree.pre_order_traversal()) print(tree.in_order_traversal()) print(tree.post_order_traversal()) print(tree.by_level_traversal()) “”” Traversal methods example 2 “”” print(“\nPDF – traversal methods example 2”) print(“———————————“) tree = BST([10, 10, -1, 5, -1]) print(tree.pre_order_traversal()) print(tree.in_order_traversal()) print(tree.post_order_traversal()) print(tree.by_level_traversal()) “”” Comprehensive example 1 “”” print(“\nComprehensive example 1”) print(“———————–“) tree = BST() header = ‘Value Size Height Leaves Unique ‘ header += ‘Complete? Full? Perfect?’ print(header) print(‘-‘ * len(header)) print(f’ N/A {tree.size():6} {tree.height():7} ‘, f'{tree.count_leaves():7} {tree.count_unique():8} ‘, f'{str(tree.is_complete()):10}’, f'{str(tree.is_full()):7} ‘, f'{str(tree.is_perfect())}’) for value in [10, 5, 3, 15, 12, 8, 20, 1, 4, 9, 7]: tree.add(value) print(f'{value:5} {tree.size():6} {tree.height():7} ‘, f'{tree.count_leaves():7} {tree.count_unique():8} ‘, f'{str(tree.is_complete()):10}’, f'{str(tree.is_full()):7} ‘, f'{str(tree.is_perfect())}’) print() print(tree.pre_order_traversal()) print(tree.in_order_traversal()) print(tree.post_order_traversal()) print(tree.by_level_traversal()) “”” Comprehensive example 2 “”” print(“\nComprehensive example 2”) print(“———————–“) tree = BST() header = ‘Value Size Height Leaves Unique ‘ header += ‘Complete? Full? Perfect?’ print(header) print(‘-‘ * len(header)) print(f’N/A {tree.size():6} {tree.height():7} ‘, f'{tree.count_leaves():7} {tree.count_unique():8} ‘, f'{str(tree.is_complete()):10}’, f'{str(tree.is_full()):7} ‘, f'{str(tree.is_perfect())}’) for value in ‘DATA STRUCTURES’: tree.add(value) print(f'{value:5} {tree.size():6} {tree.height():7} ‘, f'{tree.count_leaves():7} {tree.count_unique():8} ‘, f'{str(tree.is_complete()):10}’, f'{str(tree.is_full()):7} ‘, f'{str(tree.is_perfect())}’) print(”, tree.pre_order_traversal(), tree.in_order_traversal(), tree.post_order_traversal(), tree.by_level_traversal(), sep=’\n’)

Name:________________ Question#:_____

38

17

9

2 15

19

18 34

50

45

43 47

90

75 101

does it live in the water?

is it a mammal?

does it climb trees?

cat dogwhale sea turtle

Yes

Yes No

No

Yes No

BY LEVEL TRAVERSAL TEST 1 (0.0/2.5)

Description : This is the same test as in PDF Examples

Input : TREE pre order { 10, 5, 7, 20, 15, 12, 17 }

: TREE post order { 7, 5, 12, 17, 15, 20, 10 }

: Operation – by_level_traversal

Expected : TREE pre order { 10, 5, 7, 20, 15, 12, 17 }

: TREE post order { 7, 5, 12, 17, 15, 20, 10 }

: Method return value = QUEUE { 10, 5, 20, 7, 15, 12, 17 }

Student : TREE pre order { 10, 5, 7, 20, 15, 12, 17 }

: TREE post order { 7, 5, 12, 17, 15, 20, 10 }

: Method return value = QUEUE { 10, 5, 20, 7, 15 }

Test Failed: False is not true

BY LEVEL TRAVERSAL TEST 2 (0.0/2.5)

Description : BST by_level_traversal: Testing with random values

Input : TREE pre order { -86268, -98171, -95443, -98171, -98171, 89478, 24962, -14051, -62312, -68539, -74848, -77153, -86268, -74848, -67100, -68539, -63422, -37280, -57726, -37280, -37280, -31709, -37280, -31303, -23099, -23099, 18331, 8433, -7240, -10362, -14051, -14051, -10362, -10362, 2767, -1242, -7240, -7240, -1432, 3065, 2767, 2767, 3065, 3065, 11149, 8433, 11149, 11149, 18326, 11149, 18326, 18331, 52525, 36635, 35940, 24962, 27683, 27683, 60339, 56746, 53519, 52525, 53519, 56521, 58190, 56746, 60339, 62292, 60339, 60339, 73971, 65312, 62704, 62292, 62292, 62704, 62704, 73971, 97449, 97712, 97449, 97449, 97712, 97712 }

: TREE post order { -98171, -98171, -95443, -98171, -86268, -77153, -74848, -74848, -68539, -63422, -67100, -68539, -57726, -37280, -23099, -23099, -31303, -31709, -37280, -37280, -37280, -62312, -14051, -14051, -10362, -10362, -10362, -1432, -7240, -7240, -1242, 2767, 2767, 3065, 3065, 3065, 2767, -7240, 8433, 11149, 18326, 18326, 11149, 11149, 11149, 8433, 18331, 18331, -14051, 27683, 27683, 24962, 35940, 36635, 52525, 56521, 53519, 53519, 56746, 58190, 56746, 60339, 60339, 62292, 62292, 62704, 62704, 62704, 65312, 73971, 73971, 62292, 60339, 60339, 52525, 24962, 97449, 97449, 97712, 97712, 97712, 97449, 89478, -86268 }

: Operation – by_level_traversal

Expected : TREE pre order { -86268, -98171, -95443, -98171, -98171, 89478, 24962, -14051, -62312, -68539, -74848, -77153, -86268, -74848, -67100, -68539, -63422, -37280, -57726, -37280, -37280, -31709, -37280, -31303, -23099, -23099, 18331, 8433, -7240, -10362, -14051, -14051, -10362, -10362, 2767, -1242, -7240, -7240, -1432, 3065, 2767, 2767, 3065, 3065, 11149, 8433, 11149, 11149, 18326, 11149, 18326, 18331, 52525, 36635, 35940, 24962, 27683, 27683, 60339, 56746, 53519, 52525, 53519, 56521, 58190, 56746, 60339, 62292, 60339, 60339, 73971, 65312, 62704, 62292, 62292, 62704, 62704, 73971, 97449, 97712, 97449, 97449, 97712, 97712 }

: TREE post order { -98171, -98171, -95443, -98171, -86268, -77153, -74848, -74848, -68539, -63422, -67100, -68539, -57726, -37280, -23099, -23099, -31303, -31709, -37280, -37280, -37280, -62312, -14051, -14051, -10362, -10362, -10362, -1432, -7240, -7240, -1242, 2767, 2767, 3065, 3065, 3065, 2767, -7240, 8433, 11149, 18326, 18326, 11149, 11149, 11149, 8433, 18331, 18331, -14051, 27683, 27683, 24962, 35940, 36635, 52525, 56521, 53519, 53519, 56746, 58190, 56746, 60339, 60339, 62292, 62292, 62704, 62704, 62704, 65312, 73971, 73971, 62292, 60339, 60339, 52525, 24962, 97449, 97449, 97712, 97712, 97712, 97449, 89478, -86268 }

: Method return value = QUEUE { -86268, -98171, 89478, -95443, 24962, 97449, -98171, -14051, 52525, 97712, -98171, -62312, 18331, 36635, 60339, 97449, 97712, -68539, -37280, 8433, 18331, 35940, 56746, 60339, 97449, 97712, -74848, -67100, -57726, -37280, -7240, 11149, 24962, 53519, 58190, 62292, -77153, -74848, -68539, -63422, -37280, -10362, 2767, 8433, 11149, 27683, 52525, 53519, 56746, 60339, 73971, -86268, -31709, -14051, -10362, -1242, 3065, 11149, 27683, 56521, 60339, 65312, 73971, -37280, -31303, -14051, -10362, -7240, 2767, 3065, 18326, 62704, -23099, -7240, 2767, 3065, 11149, 18326, 62292, 62704, -23099, -1432, 62292, 62704 }

Student : TREE pre order { -86268, -98171, -95443, -98171, -98171, 89478, 24962, -14051, -62312, -68539, -74848, -77153, -86268, -74848, -67100, -68539, -63422, -37280, -57726, -37280, -37280, -31709, -37280, -31303, -23099, -23099, 18331, 8433, -7240, -10362, -14051, -14051, -10362, -10362, 2767, -1242, -7240, -7240, -1432, 3065, 2767, 2767, 3065, 3065, 11149, 8433, 11149, 11149, 18326, 11149, 18326, 18331, 52525, 36635, 35940, 24962, 27683, 27683, 60339, 56746, 53519, 52525, 53519, 56521, 58190, 56746, 60339, 62292, 60339, 60339, 73971, 65312, 62704, 62292, 62292, 62704, 62704, 73971, 97449, 97712, 97449, 97449, 97712, 97712 }

: TREE post order { -98171, -98171, -95443, -98171, -86268, -77153, -74848, -74848, -68539, -63422, -67100, -68539, -57726, -37280, -23099, -23099, -31303, -31709, -37280, -37280, -37280, -62312, -14051, -14051, -10362, -10362, -10362, -1432, -7240, -7240, -1242, 2767, 2767, 3065, 3065, 3065, 2767, -7240, 8433, 11149, 18326, 18326, 11149, 11149, 11149, 8433, 18331, 18331, -14051, 27683, 27683, 24962, 35940, 36635, 52525, 56521, 53519, 53519, 56746, 58190, 56746, 60339, 60339, 62292, 62292, 62704, 62704, 62704, 65312, 73971, 73971, 62292, 60339, 60339, 52525, 24962, 97449, 97449, 97712, 97712, 97712, 97449, 89478, -86268 }

: Method return value = QUEUE { -86268, -98171, 89478, -95443, 24962, 97449, -98171, -14051, 52525, 97712, -98171, -62312, 18331, 36635, 60339, 97449, 97712, -68539, -37280, 8433, 18331, 35940, 56746, 60339, 97449, 97712, -74848, -67100, -57726, -37280, -7240, 11149, 24962, 53519, 58190, 62292, -77153, -74848, -68539, -63422, -37280, -10362, 2767, 8433, 11149, 27683, 52525, 53519, 56746, 60339, 73971, -86268, -31709, -14051, -10362, -1242, 3065, 11149, 27683, 56521, 60339, 65312, 73971, -37280, -31303, -14051, -10362, -7240, 2767, 3065, 18326, 62704, -23099, -7240, 2767, 3065, 11149, 18326, 62292, 62704 }

Test Failed: False is not true

COUNT UNIQUE TEST 1 (0.0/1.5)

Description : This is the same test as in PDF Comprehensive Examples

Input : TREE pre order { 10 }

: TREE post order { 10 }

: Operation – count_unique()

Expected : TREE pre order { 10 }

: TREE post order { 10 }

: Method return value = 1

Student : TREE pre order { 10 }

: TREE post order { 10 }

: Method return value = 0

Test Failed: False is not true

IS PERFECT TEST 1 (0.0/3.0)

Description : This is the same test as in PDF Comprehensive Examples

Input : TREE pre order { 10, 5 }

: TREE post order { 5, 10 }

: Operation – is_perfect()

Expected : TREE pre order { 10, 5 }

: TREE post order { 5, 10 }

: Method return value = False

Student : TREE pre order { 10, 5 }

: TREE post order { 5, 10 }

: Method return value = True

Test Failed: False is not true

POST ORDER TRAVERSAL TEST 1 (0.0/1.5)

Description : This is the same test as in PDF Examples

Input : TREE pre order { 10, 5, 7, 20, 15, 12, 17 }

: TREE post order { 7, 5, 12, 17, 15, 20, 10 }

: Operation – post_order_traversal

Expected : TREE pre order { 10, 5, 7, 20, 15, 12, 17 }

: TREE post order { 7, 5, 12, 17, 15, 20, 10 }

: Method return value = QUEUE { 7, 5, 12, 17, 15, 20, 10 }

Student : TREE pre order { 10, 5, 7, 20, 15, 12, 17 }

: TREE post order { 7, 5, 12, 17, 15, 20, 10 }

: Method return value = QUEUE { 5, 7, 20, 15, 12, 17, 10 }

Test Failed: False is not true

POST ORDER TRAVERSAL TEST 2 (0.0/1.5)

Description : BST post_order_traversal: Testing with random values

Input : TREE pre order { 6030, -781, -54150, -88888, -95907, -88888, -88888, -88888, -54150, 909, -781, 909, 55591, 54714, 6030, 54714, 54714, 95790, 70552, 55591, 68258, 68021, 55591, 68258, 89818, 70552, 89818, 93578 }

: TREE post order { -95907, -88888, -88888, -88888, -88888, -54150, -54150, -781, 909, 909, -781, 6030, 54714, 54714, 54714, 55591, 68021, 68258, 68258, 55591, 70552, 93578, 89818, 89818, 70552, 95790, 55591, 6030 }

: Operation – post_order_traversal

Expected : TREE pre order { 6030, -781, -54150, -88888, -95907, -88888, -88888, -88888, -54150, 909, -781, 909, 55591, 54714, 6030, 54714, 54714, 95790, 70552, 55591, 68258, 68021, 55591, 68258, 89818, 70552, 89818, 93578 }

: TREE post order { -95907, -88888, -88888, -88888, -88888, -54150, -54150, -781, 909, 909, -781, 6030, 54714, 54714, 54714, 55591, 68021, 68258, 68258, 55591, 70552, 93578, 89818, 89818, 70552, 95790, 55591, 6030 }

: Method return value = QUEUE { -95907, -88888, -88888, -88888, -88888, -54150, -54150, -781, 909, 909, -781, 6030, 54714, 54714, 54714, 55591, 68021, 68258, 68258, 55591, 70552, 93578, 89818, 89818, 70552, 95790, 55591, 6030 }

Student : TREE pre order { 6030, -781, -54150, -88888, -95907, -88888, -88888, -88888, -54150, 909, -781, 909, 55591, 54714, 6030, 54714, 54714, 95790, 70552, 55591, 68258, 68021, 55591, 68258, 89818, 70552, 89818, 93578 }

: TREE post order { -95907, -88888, -88888, -88888, -88888, -54150, -54150, -781, 909, 909, -781, 6030, 54714, 54714, 54714, 55591, 68021, 68258, 68258, 55591, 70552, 93578, 89818, 89818, 70552, 95790, 55591, 6030 }

: Method return value = QUEUE { -781, -54150, -88888, -95907, -88888, -88888, -88888, -54150, 909, -781, 909, 55591, 54714, 6030, 54714, 54714, 95790, 70552, 55591, 68258, 68021, 55591, 68258, 89818, 70552, 89818, 93578, 6030 }

Test Failed: False is not true

CS261 Data Structures

Assignment 4

v 1.04 (revised 10/15/2020)

Your Very Own Binary Search Tree

CS261 Data Structures Project 4: Your Very Own Binary Search Tree

Contents

General Instructions​ .​………………………………………………. 3

Part 1 – Binary Search Tree Implementation

Summary and Specific Instructions​ ​ ………………………………. 4 add() ​ ……………………………………………………………………. 5 contains() ​ ……………………………………………………………….6 get_first() ​ ……………………………………………………………….6 remove() ​ ………………………………………………………………..7 remove_first() ​ ………………………………………………………….9

pre_order_traversal()​ ………………………………………………… 11 in_order_traversal() ​……………………………………………………11 post_order_traversal() ​ ………………………………………………. 11 by_level_traversal() ​……………………………………………………11

size() ​……………………………………………………………………..12 height() ​…………………………………………………………………. 12 count_leaves() ​……………………………………………………….. 12 count_unique() ​………………………………………………………… 12

is_compete() ​…………………………………………………………… 12 is_full() ​………………………………………………………………….. 12 is_perfect() ​………………………………………………………………12

Comprehensive Example #1 ​………………………………………… 13 Comprehensive Example #2 ​………………………………………… 15

Page 2 of 16

CS261 Data Structures Project 4: Your Very Own Binary Search Tree

General Instructions

1. Programs in this assignment must be written in Python v3 and submitted to

Gradescope before the due date specified in the syllabus. You may resubmit your

code as many times as necessary. Gradescope allows you to choose which

submission will be graded.

2. In Gradescope, your code will run through several tests. Any failed tests will provide

a brief explanation of testing conditions to help you with troubleshooting. Your goal

is to pass all tests.

3. We encourage you to create your own test programs and cases even though this

work won’t have to be submitted and won’t be graded. Gradescope tests are limited

in scope and may not cover all edge cases. Your submission must work on all valid

inputs. We reserve the right to test your submission with more tests than

Gradescope.

4. Your code must have an appropriate level of comments. ​At a minimum, each method should have a descriptive docstring. Additionally, put comments throughout the code

to make it easy to follow and understand.

5. You will be provided with a starter “skeleton” code, on which you will build your

implementation. Methods defined in skeleton code must retain their names and input

/ output parameters. Variables defined in skeleton code must also retain their

names. We will only test your solution by making calls to methods defined in the

skeleton code and by checking values of variables defined in the skeleton code.

You can add more helper methods and variables, as needed. You also are allowed to

add optional parameters to method definitions (may be especially helpful when

writing recursive solutions).

However, certains classes and methods cannot be changed in any way. Please see

comments in the skeleton code for guidance. In particular, content of any methods

pre-written for you as part of the skeleton code must not be changed.

6. Both the skeleton code and code examples provided in this document are part of

assignment requirements. They have been carefully selected to demonstrate

requirements for each method. Refer to them for the detailed description of expected

method behavior, input / output parameters, and handling of edge cases. Code

examples may include assignment requirements not explicitly stated elsewhere.

7. For each method, you can choose to implement a recursive or iterative solution.

When using a recursive solution, be aware of maximum recursion depths on large

inputs. We will specify the maximum input size that your solution must handle.

Page 3 of 16

CS261 Data Structures Project 4: Your Very Own Binary Search Tree

Part 1 – Summary and Specific Instructions

1. Implement a BST class by completing provided skeleton code in the file ​bst.py​. Once

completed, your implementation will include the following methods:

add(), contains(), remove()

get_first(), remove_first()

pre_order_traversal()

in_order_traversal()

post_order_traversal()

by_level_traversal()

size(), height()

count_leaves()

count_unique()

is_complete(), is_full(), is_perfect()

2. We will test your implementation with different types of objects, not just integers.

We guarantee that all such objects will have correct implementation of methods

__eq__, __lt__, __gt__, __ge__, __le__ and __str__.

3. The number of objects stored in the tree will be between 0 and 900, inclusive.

4. Tree must allow for duplicate values. When comparing objects, values less then

current node must be put in the left subtree, values greater than or equal to current

node must be put in the right subtree.

5. When removing a node, replace it with the leftmost child of the right subtree (aka

in-order successor). If the deleted node only has the left subtree, replace the deleted

node with the root node of the left subtree.

6. Variables in TreeNode and BST classes are not private. You are allowed to access and

change their values directly. You do not need to write any getter or setter methods

for them.

7. RESTRICTIONS: You are not allowed to use ANY built-in Python data structures

and/or their methods.

In case you need ‘helper’ data structures in your solution, skeleton code includes

prewritten implementation of Queue and Stack classes. You are allowed to create

and use objects from those classes in your implementation.

You are not allowed to directly access any variables of the Queue or Stack classes.

All work must be done only by using class methods.

Page 4 of 16

CS261 Data Structures Project 4: Your Very Own Binary Search Tree

add​(self, new_value: object) -> None:

This method adds new value to the tree, maintaining BST property. Duplicates must be

allowed and placed in the right subtree.

Example #1:

tree = BST()

print(tree)

tree.add(10)

tree.add(15)

tree.add(5)

print(tree)

tree.add(15)

tree.add(15)

print(tree)

tree.add(5)

print(tree)

​Output​: TREE in order { }

TREE in order { 5, 10, 15 }

TREE in order { 5, 10, 15, 15, 15 }

TREE in order { 5, 5, 10, 15, 15, 15 }

Example #2:

tree = BST()

tree.add(10)

tree.add(10)

print(tree)

tree.add(-1)

print(tree)

tree.add(5)

print(tree)

tree.add(-1)

print(tree)

​Output: TREE in order { 10, 10 }

TREE in order { -1, 10, 10 }

TREE in order { -1, 5, 10, 10 }

TREE in order { -1, -1, 5, 10, 10 }

Page 5 of 16

CS261 Data Structures Project 4: Your Very Own Binary Search Tree

contains​(self, value: object) -> bool:

This method returns True if the value parameter is in the BinaryTree or False if it is not in

the tree. If the tree is empty, the method should return False.

Example #1:

tree = BST([10, 5, 15])

print(tree.contains(15))

print(tree.contains(-10))

print(tree.contains(15))

​Output: True

False

True

Example #2:

tree = BST()

print(tree.contains(0))

​Output: False

get_first​(self) -> object:

This method returns the value stored at the root node. If the BinaryTree is empty, this

method returns None.

Example #1:

tree = BST()

print(tree.get_first())

tree.add(10)

tree.add(15)

tree.add(5)

print(tree.get_first())

print(tree)

​Output:​None 10

TREE in order { 5, 10, 15 }

Page 6 of 16

CS261 Data Structures Project 4: Your Very Own Binary Search Tree

remove​(self, value: object) -> bool:

This method should remove the first instance of the object in the BinaryTree. The method

must return True if the value is removed from the BinaryTree and otherwise return False.

NOTE: See ‘Specific Instructions’ for explanation of which node replaces the deleted node.

Example #1:

tree = BST([10, 5, 15])

print(tree.remove(7))

print(tree.remove(15))

print(tree.remove(15))

​Output: False

True

False

Example #2:

tree = BST([10, 20, 5, 15, 17, 7, 12])

print(tree.remove(20))

print(tree)

​Output: True

TREE in order { 5, 7, 10, 12, 15, 17 }

Page 7 of 16

CS261 Data Structures Project 4: Your Very Own Binary Search Tree

Example #3:

tree = BST([10, 5, 20, 18, 12, 7, 27, 22, 18, 24, 22, 30])

print(tree.remove(20))

print(tree)

# comment out the following lines

# if you have not yet implemented traversal methods

print(tree.pre_order_traversal())

print(tree.in_order_traversal())

print(tree.post_order_traversal())

print(tree.by_level_traversal())

​Output: True

TREE in order { 5, 7, 10, 12, 18, 18, 22, 22, 24, 27, 30 }

QUEUE { 10, 5, 7, 22, 18, 12, 18, 27, 24, 22, 30 }

QUEUE { 5, 7, 10, 12, 18, 18, 22, 22, 24, 27, 30 }

QUEUE { 7, 5, 12, 18, 18, 22, 24, 30, 27, 22, 10 }

QUEUE { 10, 5, 22, 7, 18, 27, 12, 18, 24, 30, 22 }

Page 8 of 16

CS261 Data Structures Project 4: Your Very Own Binary Search Tree

remove_first​(self) -> bool:

This method must remove the root node in the BinaryTree. The method must return False if

the tree is empty and there is no root node to remove and True if the root is removed.

NOTE: See ‘Specific Instructions’ for explanation of which node replaces the deleted node.

Example #1:

tree = BST([10, 15, 5])

print(tree.remove_first())

print(tree)

​Output: True

TREE in order { 5, 15 }

Example #2:

tree = BST([10, 20, 5, 15, 17, 7])

print(tree.remove_first())

print(tree)

​Output: True

TREE in order { 5, 7, 15, 17, 20 }

Page 9 of 16

CS261 Data Structures Project 4: Your Very Own Binary Search Tree

Example #3:

tree = BST([10, 10, -1, 5, -1])

print(tree.remove_first(), tree)

print(tree.remove_first(), tree)

print(tree.remove_first(), tree)

print(tree.remove_first(), tree)

print(tree.remove_first(), tree)

print(tree.remove_first(), tree)

​Output: True TREE in order { -1, -1, 5, 10 }

True TREE in order { -1, -1, 5 }

True TREE in order { -1, 5 }

True TREE in order { 5 }

True TREE in order { }

False TREE in order { }

Page 10 of 16

CS261 Data Structures Project 4: Your Very Own Binary Search Tree

pre_order_traversal​(self) -> Queue: in_order_traversal​(self) -> Queue: post_order_traversal​(self) -> Queue: by_level_traversal​(self) -> Queue:

These methods will perform pre-order, in-order, post-order, or by-level traversal of the tree,

respectively, and return a Queue object that contains values of visited nodes, in the order

they were visited. If the tree has no nodes, these methods should return an empty Queue.

Example #1:

tree = BST([10, 20, 5, 15, 17, 7, 12])

print(tree.pre_order_traversal())

print(tree.in_order_traversal())

print(tree.post_order_traversal())

print(tree.by_level_traversal())

​Output: QUEUE { 10, 5, 7, 20, 15, 12, 17 }

QUEUE { 5, 7, 10, 12, 15, 17, 20 }

QUEUE { 7, 5, 12, 17, 15, 20, 10 }

QUEUE { 10, 5, 20, 7, 15, 12, 17 }

Example #2:

tree = BST([10, 10, -1, 5, -1])

print(tree.pre_order_traversal())

print(tree.in_order_traversal())

print(tree.post_order_traversal())

print(tree.by_level_traversal())

​Output: QUEUE { 10, -1, 5, -1, 10 }

QUEUE { -1, -1, 5, 10, 10 }

QUEUE { -1, 5, -1, 10, 10 }

QUEUE { 10, -1, 10, 5, -1 }

Page 11 of 16

CS261 Data Structures Project 4: Your Very Own Binary Search Tree

size​(self) -> int:

This method returns the total number of nodes in the tree. See comprehensive examples 1

and 2 below for more details.

height​(self) -> int:

This method returns the height of the binary tree. Empty tree has a height of -1. Tree

consisting of just a single root node should return a height of 0. See comprehensive

examples 1 and 2 below for more details.

count_leaves​(self) -> int:

This method returns the number of nodes in the tree that have no children. If the tree is

empty, this method should return 0. See comprehensive examples 1 and 2 below for more

details.

count_unique​(self) -> int:

This method returns the count of unique values stored in the tree. If all values stored in the

tree are distinct (no duplicates), this method will return the same result as the size()

method. See comprehensive examples 1 and 2 below for more details.

is_complete​(self) -> bool:

This method returns True if the current tree is a ‘complete binary tree’. Empty tree is

considered complete. Tree consisting of a single root node is complete. See comprehensive

examples 1 and 2 below for more details.

is_full​(self) -> bool:

This method returns True if the current tree is a ‘full binary tree’. Empty tree is considered

‘full’. Tree consisting of a single root node is ‘full’. See comprehensive examples 1 and 2

below for more details.

is_perfect​(self) -> bool:

This method returns True if the current tree is a ‘perfect binary tree’. Empty tree is

considered ‘perfect’. Tree consisting of a single root node is ‘perfect’. See comprehensive

examples 1 and 2 below for more details.

Page 12 of 16

CS261 Data Structures Project 4: Your Very Own Binary Search Tree

Comprehensive Example #1:

tree = BST()

header = ‘Value Size Height Leaves Unique ‘

header += ‘Complete? Full? Perfect?’

print(header)

print(‘-‘ * len(header))

print(f’ N/A {tree.size():6} {tree.height():7} ‘,

f'{tree.count_leaves():7} {tree.count_unique():8} ‘,

f'{str(tree.is_complete()):10}’,

f'{str(tree.is_full()):7} ‘,

f'{str(tree.is_perfect())}’)

for value in [10, 5, 3, 15, 12, 8, 20, 1, 4, 9, 7]:

tree.add(value)

print(f'{value:5} {tree.size():6} {tree.height():7} ‘,

f'{tree.count_leaves():7} {tree.count_unique():8} ‘,

f'{str(tree.is_complete()):10}’,

f'{str(tree.is_full()):7} ‘,

f'{str(tree.is_perfect())}’)

print()

print(tree.pre_order_traversal())

print(tree.in_order_traversal())

print(tree.post_order_traversal())

print(tree.by_level_traversal())

​Output: Value Size Height Leaves Unique Complete? Full? Perfect?

———————————————————————

N/A 0 -1 0 0 True True True

10 1 0 1 1 True True True

5 2 1 1 2 True False False

3 3 2 1 3 False False False

15 4 2 2 4 True False False

12 5 2 2 5 False False False

8 6 2 3 6 True False False

20 7 2 4 7 True True True

1 8 3 4 8 True False False

4 9 3 5 9 True True False

9 10 3 5 10 False False False

7 11 3 6 11 True True False

QUEUE { 10, 5, 3, 1, 4, 8, 7, 9, 15, 12, 20 }

QUEUE { 1, 3, 4, 5, 7, 8, 9, 10, 12, 15, 20 }

QUEUE { 1, 4, 3, 7, 9, 8, 5, 12, 20, 15, 10 }

QUEUE { 10, 5, 15, 3, 8, 12, 20, 1, 4, 7, 9 }

Page 13 of 16

CS261 Data Structures Project 4: Your Very Own Binary Search Tree

Page 14 of 16

CS261 Data Structures Project 4: Your Very Own Binary Search Tree

Comprehensive Example #2:

tree = BST()

header = ‘Value Size Height Leaves Unique ‘

header += ‘Complete? Full? Perfect?’

print(header)

print(‘-‘ * len(header))

print(f’N/A {tree.size():6} {tree.height():7} ‘,

f'{tree.count_leaves():7} {tree.count_unique():8} ‘,

f'{str(tree.is_complete()):10}’,

f'{str(tree.is_full()):7} ‘,

f'{str(tree.is_perfect())}’)

for value in ‘DATA STRUCTURES’:

tree.add(value)

print(f'{value:5} {tree.size():6} {tree.height():7} ‘,

f'{tree.count_leaves():7} {tree.count_unique():8} ‘,

f'{str(tree.is_complete()):10}’,

f'{str(tree.is_full()):7} ‘,

f'{str(tree.is_perfect())}’)

print(”, tree.pre_order_traversal(), tree.in_order_traversal(),

tree.post_order_traversal(), tree.by_level_traversal(),

sep=’\n’)

​Output: Value Size Height Leaves Unique Complete? Full? Perfect?

———————————————————————

N/A 0 -1 0 0 True True True

D 1 0 1 1 True True True

A 2 1 1 2 True False False

T 3 1 2 3 True True True

A 4 2 2 3 False False False

5 2 3 4 True True False

S 6 2 3 5 True False False

T 7 2 4 5 True True True

R 8 3 4 6 False False False

U 9 3 4 7 False False False

C 10 3 4 8 False False False

T 11 4 4 8 False False False

U 12 4 5 8 False False False

R 13 4 5 8 False False False

E 14 4 6 9 False False False

S 15 4 7 9 False False False

QUEUE { D, A, , A, C, T, S, R, E, R, S, T, U, T, U }

QUEUE { , A, A, C, D, E, R, R, S, S, T, T, T, U, U }

QUEUE { , C, A, A, E, R, R, S, S, T, U, U, T, T, D }

QUEUE { D, A, T, , A, S, T, C, R, S, U, E, R, T, U }

Page 15 of 16

CS261 Data Structures Project 4: Your Very Own Binary Search Tree

Page 16 of 16

Order your essay today and save 10% with the discount code ESSAYHELP