sum of nodes in a tree.

Hello,I have a tree with "x" in the root.
How can I print the sum of these node?
Is it possible to implement it with a recursive function?

print these 16 sums:
x
x+64
x+64+256
x+64+256+1024
x+64+256+1024+4096
x+64+256+4096
x+64+1024
x+64+1024+4096
x+64+4096

x+256
x+256+1024
x+256+1024+4096
x+256+4096

x+1024
x+1024+4096

x+4096
we probably need more info.
the sums you describe cannot be done in a binary tree, so that means we need to know what you have stored, and how.
that is, to say,

1
2
3
4
5

              ****x***********
            /   |      |       \
          64   256   1024     4096

that may be doable, but as you can see its 4 child tree not 2.

it may also be possible to rig up some binary tree scheme where some nodes are on or off for each set of sums, like red-black concept with a twist, but here again, you need to describe it.

there may be a better way to rig the math. this is 2 to the 6,8,10, and 12. But it is not every possible summation of those, just some of them. I don't see a pattern, but that is the key, if you can describe the pattern, then you can make something that will do it.
Last edited on
Yes it is not a binary tree.
It is a part of a bigger problem, What I wrote is a small part.

If we have "n" as input. (n=6, n=8, n=10, n=12, ...)
Their matrices are: 64x64, 256x256, 1024x1024, 4096x4096 and ...
I wanna add x into some nodes of row one of these matrices.
these sums:
for n=6: x
for n=8: x, x+2^6
for n=10: x, x+2^6, x+2^6+2^8, x+2^8
for n=12 x, x+2^6, x+2^6+2^8 , x+2^6+2^8+2^10, x+2^6+2^10 + x+2^8, x+2^8+2^10, x+2^10

for n=14, the tree has 4 children:
child 64: has 3 chilren(256(2children:1024-4096))-1024(1child:4096)-4096)
child 256: has 2 chilren(1024(1child:4096)-4096)
child 1024: has 1 chilren(4096)
child 4096: has no chilren
This means, we have 16 sums:
x
x+64
x+64+256
x+64+256+1024
x+64+256+1024+4096
x+64+256+4096
x+64+1024
x+64+1024+4096
x+64+4096

x+256
x+256+1024
x+256+1024+4096
x+256+4096

x+1024
x+1024+4096

x+4096
Looks like you don't "have a tree", but want to enumerate some values. Recursion, perhaps?

Btw, why the change of style between "2^6" and "64"?

Furthermore, you list:
1 sum for n=6
2 sums for n=8
4 sums for n=10
7 sums for n=12 (typo or I'm blind?)
16 sums for n=14
No difference between 2^6 and 64. Both are the same.
8 sums for n=12
I can't find a way to stuff it into a tree that isnt more work than you really need.
I think if you arranged negative entries in there to get rid of some terms, ok, it may be possible, but you need to draw up the tree and figure it out if you want to go there.
I think you can solve it with iteration, which could mean recursion, or not. It looks like a standard permutation type problem where you want every combination of sums of the numbers?
Last edited on
Looks like possible:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// my first program in C++
#include <iostream>
#include <string>

void foo( std::string sum, int d, int N )
{
  std::cout << sum << '\n';
  for ( int b = d; b < N; b += 2 ) {
    foo( sum + " + 2^" + std::to_string(b), b + 2, N );
  }
}

int main()
{
  foo( "x", 6, 14 );
}

x
x + 2^6
x + 2^6 + 2^8
x + 2^6 + 2^8 + 2^10
x + 2^6 + 2^8 + 2^10 + 2^12
x + 2^6 + 2^8 + 2^12
x + 2^6 + 2^10
x + 2^6 + 2^10 + 2^12
x + 2^6 + 2^12
x + 2^8
x + 2^8 + 2^10
x + 2^8 + 2^10 + 2^12
x + 2^8 + 2^12
x + 2^10
x + 2^10 + 2^12
x + 2^12
Last edited on
I think the "tree" bit is a red herring. I'd go with Keskiverto's solution. It's a lot clearer than the original question.
Yes, it's not a complete tree, just a part of it. I agree, Keskiverto's solution is smart.
Topic archived. No new replies allowed.