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.
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 ( ) ( ) ) ) ) 9 1
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
