Sem 1 2024/2025 | TK1143

TK 1143 Program Design

TREE
Section A:

Instruction: Answer all the following questions in the space given.

1. Given the following tree.
A B

a) Which of the above is the correct binary search tree (BST) after inserted integer data in the
following order 5, 30, 2, 40, 25, 4. Justify your answer.

B, because the bigger number is inserted on the right

b) Identify root, parent node, child node and leaf node based on answer (1a).

Root - 5 Child - 2, 30, 4, 25, 40

Parent - 5, 2, 30 Leaf - 4, 25, 40

c) Based on answer (1a), illustrates BST after insert a new node with key 19. Justify your answer.
 Sem 1 2024/2025 | TK1143

d) Illustrates the process for deleting node with key 4 followed by key 5 into a current binary search
tree on answer (1c). Justify your answer.

e) Illustrates the process for searching node with key 40 and 4 into a current binary search tree on
answer (1d). Justify your answer.

f) Based on current binary search tree on answer (1e), find inorder, preorder, postorder and level
order traversals. Tips: Inorder (LNR), Preorder (NLR), Postorder (LRN)
LNR - 2,25,19,30,40
NLR - 25,2,30,19,40
LRN - 2,19,40,30,25
 Sem 1 2024/2025 | TK1143

2. Consider the following input passage.

“ i love dessert. i like to eat cake and macaron. “

a) Sketch the diagram of Binary Search Tree represent the passage above.

b) Write the Inorder traversal for the tree above.

and cake dessert eat i like i love to macaron

 Sem 1 2024/2025 | TK1143

Section B:

1. Consider the following class BST and class BSTApp.

a) Based on the BST class below
 Sem 1 2024/2025 | TK1143

i. How many attributes are there in the Node class.

2
ii. How many attributes are there in the BST class.
1

iii. How many methods are there in the BST class.

4
iv. How many argument received by insertRec() method.

2
v. Name the method in BST class that used recursive process.
insertRec

vi. Write the code segment to implement the printPreorder() dan printPostorder() for
BST class.

b) Refer to the class BSTApp below

i. What is the output for the main method above.

ii. Draw the BST diagram that represent the tree after insert all the input as above.
 Sem 1 2024/2025 | TK1143

2. Answer the following question based on the full structure of worked-example program: List of
Unique Words using BST.
 Sem 1 2024/2025 | TK1143

a. Modify the BST class above to implement the unique word using BST.
b. Write the statement for line 8 in the UniqueWord class.
c. Write the statement for line 13 UniqueWord class.
d. Write the code segment for line 18-20 in the UniqueWord class (to add new unique
word into the tree).
e. Write the code segment to print all words in Inorder traversal.

3. Consider the following tree.

a. Name the type of tree for the above tree diagram. Justify your answer.

b. Determine the output inorder, preorder and postorder for the tree above.
 Sem 1 2024/2025 | TK1143

4. Create an application based on the following task :

• Read five words from user input.
• Display all words list from BST in ascending order.
• Read a word and delete it from BST.
• Display the most recent words list from BST in ascending order.
** Note: You need to write the main program and modify the BST class to fulfill the question
requirement.

Input Output
please stay at home covid19 Inorder: at covid19 home please stay
Delete: covid19 Recent Inorder: at home please stay

stay s a f e at home everyone Inorder : at everyone home safe stay

Delete: you you does not appear in BST
Recent Inorder : at everyone home safe
stay
 Sem 1 2024/2025 | TK1143
Section C :
There are four (5) questions given in this section. Your task is to write the program to implement data
structure Tree (BST) for each question.

FIND ELEMENT
Input Standard Input

Output Standard Output

Data Structure BST

Problem Description

Write a Java program that reads integers numbers and end with 0. Your program will need to
assign all integers into BST. Your code then will need to search one integer by user input.

Input

Input of this program is integers number that end with 0. The next integer represent the integer
that will need to search in the tree.

Output

The output of the program will display either the number is FOUND or NOT FOUND in the
tree such as the following sample input-output.

Sample input – output

Input Output
7 3 9 2 4 8 10 1 5 6 0 Number 2 is FOUND in this tree.
2
7 3 9 2 4 8 10 1 5 6 0 Number 12 is NOT FOUND in this tree.
12

** Note: You need to write the main program and modify the BST class to fulfill the question
requirement.
 Sem 1 2024/2025 | TK1143

MINIMUM AND MAXIMUM ELEMENT

Input Standard Input

Output Standard Output

Data Structure BST

Problem Description

Write a Java program that reads integers numbers and end with 0. Your program will need to
assign all integers into BST. Your code then will need to find the minimum and maximum
element in the tree.

Input

Input of this program is integers number that end with 0.

Output

Output of the program will display all the elements in the tree using preorder traversal, inorder
traversal and postorder traversal followed by the minimum and maximum element in the tree.

Sample input – output

Input Output
12 3 5 36 2 1 8 0 Preorder : 12 3 2 1 5 8 36
Inorder : 1 2 3 5 8 12 36
Postorder : 1 2 8 5 3 36 12
Minimum Element in tree is : 1
Maximum Element in tree is : 36
-1 3 5 6 23 30 18 0 Preorder : -1 3 5 6 23 18 30
Inorder : -1 3 5 6 18 23 30
Postorder : 18 30 23 6 5 3 -1
Minimum Element in tree is : -1
Maximum Element in tree is : 30

** Note: You need to write the main program and modify the BST class to fulfill the question
requirement.
 Sem 1 2024/2025 | TK1143

TREE WITH PARENTHESES

Input Standard Input

Output Standard Output

Data Structure BST

Problem Description

Write a Java program that reads a passage and assign all words into BST. Your code then
will print all the words in parentheses format as below:

(root, (sub-left tree) (sub-right tree))

Input

Input of this program is a passage. A passage consists of N words and symbols. Symbols that
will beconsidered in the passage are full stop (.), comma (,), question mark (?) and exclamation
mark (!). The passage will have M unique words, where the M is less than or equal to N.

Output

Output of the program is all the words in parentheses format.

Sample input – output

Input Output
E C A D G I. (E(C(A()())(D()()))(G()(I()())))
i go to school (i(go(by(bus(big()())())())())(to(school(is()())(the()()))()))
by bus. the bus
is big.

** Note: You need to write the main program and modify the BST class to fulfill the question
requirement.
 Sem 1 2024/2025 | TK1143

WORD FREQUENCIES

Input Standard Input

Output Standard Output

Data Structure Binary Search Tree

Problem Description
Write a JAVA program that will read all words from a passage and store them in BST. The
programthen will display a menu and perform the following task:
• Delete a word. If word exists, update the word frequency otherwise print word not exist.
• Search a word. If word exists, print the word and its frequency otherwise print not exist.
• Add a new word. If the word is in the passage, update its frequency.
• Print all words and its frequency in ascending order.

Input

Input of this program is a passage. A passage consists of N words and symbols. Symbols that
will beconsidered in the passage are full stop (.), comma (,), question mark (?) and exclamation
mark (!). The passage will have M unique words, where the M is less than or equal to N.

Followed by the input code and the required data as specified in the sample input-output.

Sample input-output

Input Output
Stay at home, stay safe and stay
healthy. Practice social distancing Menu:
at work and at home. Help reduce 1. Add new word.
the risk of infection and 2. Delete word.
preventing covid19. Together we 3. Search word.
break the chain of covid19. #kita 4. Print all words and its frequency.
jaga kita. Hapuskan covid19!. 5. Exit.
2
pendemic Input code: 2
2 Enter word to be deleted: pendemic
covid19 The word pendemic is not in the passage.
2
we Menu:
1 1. Add new word.
pendemic 2. Delete word.
4 3. Search word.
1 4. Print all words and its frequency.
social 5. Exit.
4
3 Input code: 2
home Enter word to be deleted: covid19
3
 Sem 1 2024/2025 | TK1143
work One of the words covid19 was successfully
3 deleted.
good
2 Menu:
work 1. Add new word.
2 2. Delete word.
social 3. Search word.
4 4. Print all words and its frequency.
10 5. Exit.
99
5 Input code: 2
Enter word to be deleted: we
One of the words we was successfully deleted.

Menu:
1. Add new word.
2. Delete word.
3. Search word.
4. Print all words and its frequency.
5. Exit.

Input code: 1
Enter new word: pendemic
The word pendemic has been added
successfully.

Menu:
1. Add new word.
2. Delete word.
3. Search word.
4. Print all words and its frequency.
5. Exit.

Input code: 4
Hapuskan(1)
Help(1)
Practice(1)
Stay(1)
Together(1)
and(3)
at(3)
break(1)
chain(1)
covid19(2)
distancing(1)
healthy(1)
home(2)
infection(1)
jaga(1)
kita(2)
of(2)
pendemic(1)
preventing(1)
reduce(1)
risk(1)
safe(1)
social(1)
stay(2)
the(2)
work(1)
 Sem 1 2024/2025 | TK1143

Menu:
1. Add new word.
2. Delete word.
3. Search word.
4. Print all words and its frequency.
5. Exit.

Input code: 1
Enter new word: social
The word social has been added successfully.

Menu:
1. Add new word.
2. Delete word.
3. Search word.
4. Print all words and its frequency.
5. Exit.

Input code: 4
Hapuskan(1)
Help(1)
Practice(1)
Stay(1)
Together(1)
and(3)
at(3)
break(1)
chain(1)
covid19(2)
distancing(1)
healthy(1)
home(2)
infection(1)
jaga(1)
kita(2)
of(2)
pendemic(1)
preventing(1)
reduce(1)
risk(1)
safe(1)
social(2)
stay(2)
the(2)
work(1)

Menu:
1. Add new word.
2. Delete word.
3. Search word.
4. Print all words and its frequency.
5. Exit.

Input code: 3
Input Search text: home
The word home is used 2 times.

Menu:
1. Add new word.
 Sem 1 2024/2025 | TK1143
2. Delete word.
3. Search word.
4. Print all words and its frequency.
5. Exit.

Input code: 3
Input Search text: work
The word work is used 1 times.

Menu:
1. Add new word.
2. Delete word.
3. Search word.
4. Print all words and its frequency.
5. Exit.

Input code: 3
Input Search text: good
The word good is not in the passage.

Menu:
1. Add new word.
2. Delete word.
3. Search word.
4. Print all words and its frequency.
5. Exit.

Input code: 2
Enter word to be deleted: work
One of the words work was successfully
deleted.

Menu:
1. Add new word.
2. Delete word.
3. Search word.
4. Print all words and its frequency.
5. Exit.

Input code: 2
Enter word to be deleted: social
One of the words social was successfully
deleted.

Menu:
1. Add new word.
2. Delete word.
3. Search word.
4. Print all words and its frequency.
5. Exit.

Input code: 4
Hapuskan(1)
Help(1)
Practice(1)
Stay(1)
Together(1)
and(3)
at(3)
break(1)
 Sem 1 2024/2025 | TK1143
chain(1)
covid19(2)
distancing(1)
healthy(1)
home(2)
infection(1)
jaga(1)
kita(2)
of(2)
pendemic(1)
preventing(1)
reduce(1)
risk(1)
safe(1)
social(1)
stay(2)
the(2)

Menu:
1. Add new word.
2. Delete word.
3. Search word.
4. Print all words and its frequency.
5. Exit.

Input code: 10
Invalid code, Enter code 1-5.

Menu:
1. Add new word.
2. Delete word.
3. Search word.
4. Print all words and its frequency.
5. Exit.

Input code: 99
Invalid code, Enter code 1-5.

Menu:
1. Add new word.
2. Delete word.
3. Search word.
4. Print all words and its frequency.
5. Exit.

Input code: 5
Bye..

** Note: You need to write the main program and modify the BST class to fulfill the question
requirement.
 Sem 2 2020/2021 | TK1143

Solution

The algorithm for Word Frequencies :

Read a passage
Remove unnecessary characters
For all words in the passage
Travers to find the word from the BST
If not found

add the word into the BST and with frequency = 1

else

Traverse to display all words with its frequency using in order traversal.