CST 370 –  Homework 8 

CST 370 – 
Homework 8 

How to turn in? 
•    Submit your two C++ (or Java) source files on the iLearn. 

This is the HackerRank link: https://www.hackerrank.com/cst370-s20-hw8 


1. Write a C++ (or Java) program named hw8_1.cpp (or hw8_1.java) that provides a few functions for a binary tree. For the homework, you can start from the binary tree implementation using a “struct node” at https://repl.it/@YBYUN/InorderTraversal which we covered in the class.


Input format: This is a sample input from a user. 













The first line (= 15 in the example) indicates that you have to build a binary tree with a root value 15. The second line (= 9 in the example) indicates the number of commands you have to conduct to the binary tree. The commands include “append” (= add a new number at the end of the tree), “isBST” (= checking if the binary tree is a binary search tree or not), “preOrder”, “height”, “levelOrder” (= visit the tree level-by-level from the root), “deleteLastNode”, and “postOrder”.

For instance, after the two commands “append 10” and “append 50”, you will have a binary tree like below:













Sample Run 1: Assume that the user typed the following lines

15
9
append 10
append 50
isBST
preOrder
append 45
height
levelOrder
deleteLastNode
postOrder

This is the correct output. 
true
15 10 50
2
15 10 50 45
10 50 15

For the “isBST” command, your program should display “true” because the binary tree is a binary search tree at that moment. Then, it displays the “preOrder” traversal result. After that, your program appends a number “45”. Then, it displays the height of the tree (= 2). Note that the height of an empty tree is -1.  
For the “levelOrder”, your program should display the nodes level-by-level from the root. In other words, the first number “15” is the root value of the binary tree. Then, “10” and “50” are the left child and right child of the root. Then, the “45” is the left child of “10”. 
Finally, your program deletes the last node (= 45 in the example) and displays the “postOrder”.



Sample Run 2: Assume that the user typed the following lines

20
8
append 30
append 40
append 15
append 25
append 70
isBST
inOrder
levelOrder

This is the correct output. 

false
15 30 25 20 70 40
20 30 40 15 25 70

Sample Run 3: Assume that the user typed the following lines

10
7
append 5
append 15
deleteLastNode
levelOrder
deleteLastNode
preOrder
isBST

This is the correct output. 

10 5
10
true






 
2. Write a C++ (or Java) program called hw8_2.cpp (or hw8_2.java) that conducts the topological sorting based on the source removal algorithm (= Kahn’s algorithm) covered in the class. 

Input format: This is a sample input from a user. 









The first line (= 4 in the example) indicates that there are four vertices in the graph. For the homework, you can assume that the first vertex starts from the number 0. The second line (= 5 in the example) represents the number of edges in the graph, and following five lines are the edges. This is the graph with the input data. 











Sample Run 1: Assume that the user typed the following lines

4 
5
0 1
0 2
0 3
1 3
2 3

This is the correct output. Your program should display the numbers of incoming degrees of each vertex first. For example, the vertex 3 has three incoming degrees which is represented as “In-degree[3]:3”. After the incoming degree information, your program should display the topological order as you learned in the class.

In-degree[0]:0
In-degree[1]:1
In-degree[2]:1
In-degree[3]:3
Order:0->1->2->3


Sample Run 2: Assume that the user typed the following lines

5 
4
0 1
1 2
0 2
3 4

This is the correct output. 

In-degree[0]:0
In-degree[1]:1
In-degree[2]:2
In-degree[3]:0
In-degree[4]:1
Order:0->3->1->4->2


This is the input graph.











Sample Run 3: Assume that the user typed the following lines

3 
3
0 1
1 2
2 0

This is the correct output. Note that this graph is not a DAG (= directed acyclic graph) and there’s no topological order for a non-DAG.

In-degree[0]:1
In-degree[1]:1
In-degree[2]:1
No Order: