Find sum problem

#1

input format is not clear,pls clarify the question?

#2

Hi @pradyumn2006
This particular problem asks you to take a generic tree input . A generic tree is a tree where any node can have any number of children (unlike binary trees where a node can have atmost 2 children).

The first integer in each row indicates the data at the node whereas the second integer indicates the no of children that node has .

Refer to this code for the input function - https://ide.codingblocks.com/s/90995

As for the sample testcase given in the problem
1 2
2 2
3 0
4 0
5 2
6 0
7 0
2

Here the tree looks like

                     1                                 Level 0
                /          \
              2              5                         Level 1
           /      \       /     \
          3       4      6        7                    Level 2

Sum at Level 2 = 3 + 4 + 6 + 7 = 20

Here’s another testcase for you to try
Input :
2 2
1 1
5 0
6 2
3 0
7 0
2

Expected Output : 15

Hit like if you understand.

#3

IN THE CODE OF INPUT FUNCTION GIVEN BY YOU,HOW WOULD THE NODE POINT TO ITS 3rd or 4th child.

#4

ALSO WHY YOU HAVE WRITTEN THE CONSTRUCTOR BEFORE DECLARING RIGHT AND LEFT?

#5

@pradyumn2006
As for your first doubt , this code works using recursion. I am covering the sample testcase here. First we get a node with data = 1 and noOfChildren=2 so we make a new node using this and make a recursive call on its left child first.
We get the left child as a node with data=2 and noOfChildren=2.
Then again we make a recursive call over its left child.
We get 3 with 0 children. Since this node has no children we go back to 2 and make a recursive call to its right child.
We get 4 with 0 children. We again go back to 2 and since both the children of 2 have been covered , we go back to 1 and complete its recursive call for its right child as it was still pending. We repeat the same process again to generate the tree as shown above.
The third and the fourth children are generated through recursive calls over the left part of the root node.

As for your second doubt regarding the constructor , a class is a single unit. All data members and member functions of a class know each other regardless of the order they are declared in since the entire class is compiled as single unit and not seperately. So it doesn’t matter if you declare the member functions and data variables later or if you do vice versa , it works all the same in a class.
Note that this wouldn’t work outside a class as then the compiler works line by line and would throw an error if a variable is used first in a function and then declared later.

#6

Can you explain the case in which there are 3 or more children of a particular node, since in code(given by you) node class have only 2 pointers to child nodes?

#7

@pradyumn2006
Only the input function in this question is for generic tree. It is assured that you will get a binary tree as input only i.e. tree with nodes having atmost 2 children.
In a pure generic tree , the input function and node class are absolutely different. There the node class does not have left and right pointer for children , but rather we make an array or vector of pointers in which we store the locations of the children. The size of this array is equal to noOfChildren . Those trees are not covered in this course and to be honest , they are very rarely used in general. You will hardly find questions on them even on sites like HackerEarth and HackerRank so you can leave them and just focus on Binary Trees and Binary Search Trees.

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.