By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
429,384 Members | 671 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 429,384 IT Pros & Developers. It's quick & easy.

Given an integer K and a tree in string format.how to solve below problem ?

P: 56
Given an integer K and a tree in string format. We have to print the sum of all elements at Kth level from root.

0
/ \
5 7
/ \ / \
6 4 1 3
\
9



Tree given in the form: (node value(left subtree)(right subtree))
For tree given above: (0(5(6()())(4()(9()())))(7(1()())(3()())))
Input format: K Tree
Output format: Sum
For example, for given tree:
Input: 2 (0(5(6()())(4()(9()())))(7(1()())(3()())))
Output: 14

I am unable to get the approach of starting with this , how to implement it using stack ?
Jul 8 '16 #1
Share this Question
Share on Google+
6 Replies


weaknessforcats
Expert Mod 5K+
P: 9,197
This is done using recursion.

Have you ever written a recursive function?
Jul 8 '16 #2

P: 56
Expand|Select|Wrap|Line Numbers
  1. #include<stdio.h>
  2. #include<string.h>
  3. int main()
  4. {int sum=0;
  5. char str[40];
  6. char *ptr;
  7. int k;
  8. printf("enter string");
  9. gets(str);
  10. printf("enter depth");
  11. scanf("%d",&k);
  12. ptr=str;
  13. int depth =-1;
  14. while(*ptr!='\0')
  15. {
  16. if(*ptr=='(')
  17. {
  18. depth++;
  19. if(depth==k)
  20. {
  21. sum=sum+*(++ptr)-'0';
  22. }
  23. }
  24. else if (*ptr==')')
  25. {
  26. depth--;
  27. }
  28. }
  29. printf("%d", sum);
  30. return 0;
  31. }
  32.  

Started with a depth of -1. Increment the depth when we find a (. Decrement the depth when we find a ). If I encounter a digit when depth is equal to K, then convert the digits to a number, and add the number to the sum.

But this code isn't working ,please help
Jul 9 '16 #3

weaknessforcats
Expert Mod 5K+
P: 9,197
Change the code so you don't enter the string for the tree.

The string must be (0(5(6()())(4()(9()())))(7(1()())(3()()))) exactly.

Let me know what happens.
Jul 9 '16 #4

P: 56
I am unable to get your point , I entered this string only as input .
Jul 9 '16 #5

weaknessforcats
Expert Mod 5K+
P: 9,197
The tree in the problem can only be this string:

(0(5(6()())(4()(9()())))(7(1()())(3()())))

exactly.
I have no idea what you entered but if it's not exactly this then your code won't work.

By removing the data entry you remove one reason why the code doesn't work.

After all, your program is just a test of your function to iterate the tree, it's not a full fledged app.
Jul 9 '16 #6

P: 56
I got the point , I forgot to increment the pointer , input was correct , thankss a lot
Jul 10 '16 #7

Post your reply

Sign in to post your reply or Sign up for a free account.