Recursion Help!

[simonsayz27]

Hey everyone. I first post and I couldn't figure out how to encase my code, sorry. Let me know and I'll do it next post. Anyways, I've built binary tree using recursion and included a function to print out the sum of the level of the tree of a given input by a user. My problem isn't that my function doesn't work, but it prints out to the console each levels sum where I only want the level given from the input. For example, if this is my tree:

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

it will print out:

1
5
22

where I only want it to print out 22.
Now I see in my function why is it printing out all lines, but can't figure out a different solution. I'm using a static variable to add the total up. If you suggest using a global static variable, I already tried and doesn't work. Any suggestions would really help. The function code is below and based on the tree above as a sample tree with the input -3. Thanks a ton!

void sumLevel(treeNode *&ptr, int input /* -3 */, static int depth /* == -1*/)
{
    static int depthTotal = 0;
    if(input == depth)
    {
        depthTotal = depthTotal + ptr->data;
        cout << depthTotal << endl;
        return;
    }
    if(ptr->left != NULL)
    {
        sumLevel(ptr->left, input, depth - 1); 
    }
    if(ptr->right != NULL)
    {
        sumLevel(ptr->right, input, depth - 1);
    }
}

[Rashakil Fol]

Don't use any globals (i.e. static variables) and have your function that calculates the answer be separate from the function that prints the answer.

[Tom Gunn]

input == depth will happen for every node at that depth. You only want to print the total after the function returns instead of inside the recursive function. A reference parameter would be better suited to that:

#include <iostream>

struct treeNode
{
    int data;
    treeNode* left;
    treeNode* right;

    treeNode(int data, treeNode* left, treeNode* right)
    {
        this->data = data;
        this->left = left;
        this->right = right;
    }
};

void sumLevel(treeNode *&ptr, int input, int depth, int& depthTotal)
{
    if(input == depth)
    {
        depthTotal = depthTotal + ptr->data;
        return;
    }

    if(ptr->left != NULL)
    {
        sumLevel(ptr->left, input, depth - 1, depthTotal);
    }

    if(ptr->right != NULL)
    {
        sumLevel(ptr->right, input, depth - 1, depthTotal);
    }
}

int main()
{
    treeNode* root = 
        new treeNode(1,
            new treeNode(2,
                new treeNode(4, 0, 0),
                new treeNode(5, 0, 0)),
            new treeNode(3,
                new treeNode(6, 0, 0),
                new treeNode(7, 0, 0)));
    int sum = 0;

    sumLevel(root, -3, -1, sum);
    std::cout << sum << '\n';
}

[simonsayz27]

Thanks A LOT Tom! That fixed everything.

[codewalkz]

Hi, I have a related problem: http://www.daniweb.com/forums/thread231989.html

I have a binary tree and I would like to get the number of people in each side of a specific user. For example:

1 is upline of 2 and 3

I now want to get the total number of people under under number 1 including total number of people under Number 2 and Number 3. How am I suppose to do that? Please do excuse my asking It's my first time to handle Binary trees in php. Im using Php and Mysql.

The tree looks like this:

1
                      2                                                        3
      4                           5                            5                            6
7          8            9              10            11          12          13               14

Thank you so much!