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

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

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 . 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 , 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 . 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.

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

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

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

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

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:

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

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)

print(tree)

print(tree)

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()

print(tree)

print(tree)

print(tree)

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())

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 ‘

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]:

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 ‘

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’:

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