Instructions: For the question given below, write the design in the shared doc. Upload your design as a .pdf file in the eduserver strictly by 2.30 pm in the link provided for submitting the design of the Modification question. After submitting the design, implement your design using C Language and show the output of your program to the evaluator for the test cases given for the Modification question in eduserver. In any case, you should submit your C Program in the eduserver strictly by 3.15 pm in the link provided for submitting the C Program for the Modification question. In case of clarifications, your evaluator will help you.
Marks (Design + Implementation + Viva): 3 + 3 + 2
The marks for implementation will be based on the results for the test cases. The evaluator will be conducting a viva for a maximum of 5 minutes.
QUESTION
1. SAC wants to invite maximum students from the hostels to participate in New Year’s evening. You are part of the invitation team. The hostels in NIT Calicut are arranged in the form of a binary tree T, where each node is a hostel having a unique id. Initially you are standing at the given starting hostel node. You are given an area to invite, which consists of nodes within a distance k from the starting node. Write a program to find the sum of id’s of all hostel nodes you are supposed to invite within a given distance of k from the starting hostel node. Note that the starting hostel node id should also be included in the sum.
Hint: Distance between two nodes in a binary tree is defined as the number of edges in the path between the two nodes.
31 16
45
7 24
19 29
Figure 1: The nodes with distance 1 from 16 are represented in green color.
Input format:
- The integers, if given, are in the range [0,103].
- First line of the input contains space separated Parenthesis Representation of the tree
T.
- Second line contains two integers separated by a space. First integer will be starting hostel
node id and the second integer will be the distance k. Output format:
• The output consist of a single integer value sum.
1
Sample Input 1:
( 18 ( 9 ( 3 ( 8 ( ) ( ) ) ( ) ) ( 4 ( 25 ( ) ( ) ) ( 14 ( ) ( ) ) ) ) ( 27 ( 5 ( ) ( ) ) ( 56 ( ) ( ) ) ) )
91
Sample Output 1:
34
Sample Input 2:
( 31 ( 16 ( 7 ( ) ( ) ) ( 24 ( 19 ( ) ( ) ) ( 29 ( ) ( ) ) ) ) ( 45 ( ) ( ) ) )
16 2
Sample Output 2:
171
Sample Input 3:
( 31 ( 16 ( 7 ( ) ( ) ) ( 24 ( 19 ( ) ( ) ) ( 29 ( ) ( ) ) ) ) ( 45 ( ) ( ) ) )
16 1
Sample Output 3:
78
2
