Description
PART I. Construct a Binary Tree
In the first part of the homework, you will construct a binary tree based on the positive integer
node values given in an input text file. The first line of the input file contains a series of positive
integers that will be used on tree nodes as follows. The first integer will be used as the value
of the tree root. Then, second integer (if any) will be used as the value of the left child of the
root and third integer (if any) will be used as the value of the right child of the root, and so on.
As a general rule, if the value of the parent node is i
th integer in the file, then the value of the
left child of this parent node is (2*i)th integer (if any) in the file and the value of the right child
of this parent node is (2*i+1)th integer (if any) in the file. This method fills in the tree level by
level as exemplified below:
1
2 3
4 5 6
The Tree:
The first line of the Input file: 1 2 3 4 5 6
Level 0
Level 1
Level 2
PART II. Path of a Sum in a Binary Tree
In the second part of the homework, you will find all the paths (i.e., up to two paths) that starts
from the tree root and sums up to a target number in the constructed binary tree. The target
number will be given in the second line of the input file. You have to use preorder traversal
in your searches and your found paths must start from the root. If you find one/two path(s)
that sum(s) up to the target, then output “Path Found: “ and the numbers on the path(s). If you
can find no paths, then print out “No Path Found”. Please look at the example below:
10
13 28
25 15 45
The Tree:
The first line of the Input file: 10 13 28 25 15 45 53
The second line of the Input file: 38
53
The Output: Path Found: 10 13 15
Path Found: 10 28
Data Structures Assignment 5
CAUTION: If a subtree contains any path that sums up to the target but doesn’t start from
the root of the tree, then don’t print it out. See the example below which uses the scenario
above and shows a subtree that satisfies the target sum.
10
13 28
25 15 45
A subtree that sums up to the target value 38.
Omit such subtrees, ONLY print out the trees that start from the root.
53
CAUTION: There can be more than two paths that sums up to the target and start from the
root of the tree. You have to print out only two of these paths in that case. You have to print
out the first found path on the left subtree of the root by using preorder traversal. Then, you
have to print out the first found path on the right subtree of the root by using preorder
traversal. See the example below which shows three paths that starts from the root and
satisfies the target sum. Please note that, the output only contains two paths.
10
13 28
10 15 45
Path-1: Firstly Found by
Preorder Traversal
The first line of the Input file: 10 13 28 10 15 45 53 5
The second line of the Input file: 38
53
The Output: Path Found: 10 13 10 5
Path Found: 10 28
5
Path-2
Only One Possible Path On The
Right Sub-Tree of The Root:
Path-3: 10 28 (PRINT THIS PATH OUT
SINCE IT IS FIRST
(AND LAST) PATH
FOUND ON
RIGHT-SUBTREE
OF THE ROOT)
Two Possible Paths On The
Left Sub-Tree of The Root:
Path-1: 10 13 10 5 (PRINT THIS PATH OUT
SINCE IT IS FIRST PATH FOUND
ON LEFT-SUBTREE OF THE ROOT)
Path-2: 10 13 15 (DON’T PRINT THIS PATH OUT
SINCE IT IS SECOND PATH FOUND
ON LEFT-SUBTREE OF THE ROOT)
Path-3
Compilation, Running, and Output
Your source code file name must be hw5.cpp.
Your program should compile and run on Linux environment using g++ (version 4.8.5
or later). To compile the code, use the following command:
g++ -Wall -Werror hw5.cpp -o hw5
Your input data filename will be supplied from the command line. Don’t name it
in your program statically. Your program must take input filename as command line
argument. Then run your executable (named as hw5) using the following command:
./hw5 input_file_name
Data Structures Assignment 5
where input_file_name is name of any test file we will use to evaluate your
homeworks. IF YOUR PROGRAMS DON’T TAKE FILE NAME FROM THE
COMMAND LINE, THEY WILL NOT BE EVALUATED AND BE GRADED AS 0.
As in the previous homeworks, Your program will be checked using Calico
(https://bitbucket.org/uyar/calico) automatic checker. Therefore, make sure you print
the messages exactly as given in the homework definition. You can get zero marks
if the automatic checker fails.
An example compile, run and output that finds TWO PATHS is as follows:
Compile The File: g++ -Wall -Werror hw5.cpp -o hw5
Input File (e.g., named as input.txt): 10 5 15 20 35 25 30 64 128 256 512
50
Run The Program: ./hw5 input.txt
Program Output: Path Found: 10 5 35
Path Found: 10 15 25
An example compile, run and output that finds NO PATHS is as follows:
Compile The File: g++ -Wall -Werror hw5.cpp -o hw5
Input File (e.g., no_paths.txt): 10 5 15 20 35 25 30 64 128 256 512
51
Run The Program: ./hw5 no_paths.txt
Program Output: No Path Found
Submission Rules
Do not send any e-mails regarding the HW description. If something is not clear to you,
you can ask your question under the thread that is specially started for
homework 5 (Questions about HW5) on the message board for BLG 223E on
NINOVA. Please check before writing your question whether your question is asked by
someone else. Do not share any code or text that can be submitted as part of your HW.
Make sure you write your name and number in all of the files of your project, in the
following format:
/* @Author
Student Name:
Student ID :
Date:
Only electronic submissions through Ninova will be accepted.
You should not share or copy code from your classmates or from the Internet. You
should submit your own, individual homework.
Academic dishonesty, including cheating, plagiarism, and direct copying, is
unacceptable.
Use comments wherever necessary in your code to explain what you did.
Note that YOUR CODES WILL BE CHECKED WITH THE PLAGIARISM TOOLS!
