Description

Lecturer: Prof. Jaesik Park
Teaching Assistants: ByeongHoon So, Hyunmin Lee, Junha Lee

0. Basic instruction
a. Please refer to the attached file named PA_instructions_updated.pdf

1. Quiz (2 pts)
1-1. Let T is a general tree, and T’ is a binary tree converted from T. Which of the following traversal visits the nodes in the same order as the postorder traversal of T?
(1) Preorder traversal of T’
(2) Inorder traversal of T’
(3) Postorder traversal of T’
(4) None of the aboves

1-2. What is the maximum height of a proper binary tree with n nodes?
(1) O(1)
(2) O(log n)
(3) O(n)
(4) O(2^n)

● Example execution
– If you choose “(1) Preorder traversal of T’ ” for 1-1., print your answer as shown below
>> ./pa2.exe 1 1
[Task 1]
1

– If you choose “(1) O(1) ” for 1-2., print your answer as shown below
>> ./pa2.exe 1 2
[Task 1]
1

pre-2. Construct Binary Tree

Note: pre-2 is not a problem that will be evaluated, but this is a short pre-requisite to solve problems 2,3, and 4. Don’t worry. We are providing utility functions to help you.

a. For problems 2, 3, and 4, you would need to implement member functions of BinaryTree class. To construct a BinaryTree class instance from an input, we use the string with bracket representation as input. The recursive definition of the bracket representation is as follows.
Tree = Root(LeftChild)(RightChild). Below are some examples.
The left tree is represented as 1(2)(3) , and the right tree is
1(2(4)(5))(3(6))

b. To implement “a”, we provide a function to construct BinaryTree class from the bracket representation, which is BinaryTree::buildFromString function. It creates a pointer-based BinaryTree class instance from the given string. It would be helpful to read the implementation details of
BinaryTree::buildFromString

c. To sum up, you will need to use BinaryTree class for problems 2, 3 and 4. Please try to understand the code for BinaryTree class.

2. Traverse Binary Tree (2 pts)

a. Implement BinaryTree::preOrder, BinaryTree::postOrder and BinaryTree:postOrder function that can traverse a binary tree with given traverse mode

b. Input & Output
Input:
– String with bracket representation.
– String representing traverse mode. Either “preorder ”, “ postorder ” or “inorder ” Output:
– A sequence of node values acquired from the tree traversal. The value is separated with a white space

c. Example input & output
Input Output
“1(2)(3)”, “preorder” 1 2 3
“4(2(3)(1))(6(5))”, “preorder” 4 2 3 1 6 5
“4(2(3)(1))(6(5))”, “inorder” 3 2 1 4 5 6
“4(2(3)(1))(6(5))”, “postorder” 3 1 2 5 6 4

d. Example execution
>> ./pa2.exe 2 “4(2(3)(1))(6(5))” “inorder”
[Task 2]
3 2 1 4 5 6

3. Height of Binary Tree (3 pts)

a. Implement BinaryTree::getHeight function that can calculate the height of the given binary tree

b. Input & Output
Input: A string with bracket representation
Output: height of the given tree

c. Example input & output
Input Output
1 1
1(2)(3) 2
4(2(3)(1))(6(5)) 3

d. Example execution
>> ./pa2.exe 3 “4(2(3)(1))(6(5))”
[Task 3]
3

4. Completeness of Binary Tree (3 pts)

a. Implement BinaryTree::isComplete function that can check whether if the given binary tree is a complete binary tree or not

b. Input & Output
Input: string with bracket representation
Output: string “True” if the given binary tree is complete binary tree, “False” otherwise

c. Example input & output
Input Output
1(2)(3) True
4(2(3)(1))(6(5)) True
4(2()(1))(6(5)) False

d. Example execution
>> ./pa2.exe 4 “4(2(3)(1))(6(5))”
[Task 4]
True

5. Min-heap Insertion (2 pts)

Note: For solving problems 5 and 6, the similar utility functions provided in PA1 will be used to parse an input string. Therefore, you won’t need to try implementing a string parser. Please read pa2.cpp, and find the lines where your code would be located.

a. Implement a function that inserts a new element to a binary min-heap. Your heap should maintain the min-heap property even after the insertion. Each test case will insert less than 100 values

b. Input & Output
Input: A sequence of commands
– (‘insert’,integer): insert integer into the current min heap Output:
– Values in a heap in a node number order, in a string separated with the white space (automatically printed with built-in function)
– Do not consider the exceptional cases such as overflow, underflow or empty heap. We will not use the test cases for those scenarios.

c. Example Input & Output
Input Output
[(‘insert’,5),(‘insert’,-3),(‘insert’,2)] -3 5 2
[(‘insert’,4),(‘insert’,-2),(‘insert’,9),(‘inse rt’,10),(‘insert’,15),(‘insert’,-25)] -25 4 -2 10 15
9
[(‘insert’,28),(‘insert’,9),(‘insert’,27),(‘ins ert’,10),(‘insert’,3),(‘insert’,45)] 3 9 27 28 10
45

d. Example execution
>> ./pa2.exe 5 “[(‘insert’,5),(‘insert’,3),(‘insert’,2)]”
[Task 5]
2 5 3
6. Min-heap Deletion (3 pts)

a. Implement a function that deletes the minimum value from the binary min-heap. Your heap should maintain the min heap property even after the deletion.

b. Input & Output
Input: A sequence of commands, which is one of the following
– (‘insert’,integer): insert integer into the current min heap
– (‘delMin’,NULL): delete minimum value from current binary min heap and rearrange heap to maintain the min heap property.
Output:
– Values in the a heap in a node number order, in a string separated with the white space (automatically printed with built-in function)
– Do not consider the exceptional cases such as overflow, underflow or empty heap. We will not use the test cases for those scenarios.

c. Example Input & Output
Input Output
[(‘insert’,5),(‘insert’,-3),(‘insert’,22),(‘del
Min’,NULL)] 5 22
[(‘insert’,28),(‘insert’,9),(‘insert’,27),(‘ins ert’,10),(‘insert’,3),(‘insert’,45),(‘delMin’,N ULL)] 9 10 27 28 45
[(‘insert’,28),(‘insert’,9),(‘insert’,27),(‘ins ert’,10),(‘insert’,3),(‘insert’,45),(‘delMin’,N ULL),(‘insert’,22)] 9 10 22 28 45
27

d. Example execution
>> ./pa2.exe 6 “[(‘insert’,4),(‘insert’,-2),(‘insert’,9),
(‘insert’,10),(‘insert’,15),(‘insert’,-25),(‘delMin’,NULL)]”
[Task 6]
-2 4 9 10 15