Question on Tree data structure, print each level sum ( level sum = sum of siblings data )?

Below I wrote a piece of code to answer this question. Colud you please tell me 1) if you find any defects in my code 2) any other best solution ?

Question: Question on Tree data structure, print each level sum ( level sum = sum of siblings data ) ?

struct tree{
             int data;
             struct *left;
             struct *right;
 };

API protype is void EachLevelSum(struct tree *root);

My answer is

void EachLevelSum(struct tree *root )
{
     stati开发者_JS百科c int level=0;
     static int a[100] = {0}; // I am assuming , at MAX 100 levels in tree

     if( root == NULL )
     {
           return;
     }
     else
     {
           a[level += root->data;

           level++;
           EachLevelSum(root->left);
           level--;      

           level++;
           EachLevelSum(root->right);
           level--;      

           if( level == 0 )
           {
               int i;
               for( i=0; i<100 && a[i]!=0 ; i++)
               {
                   printf("\n level: %d sum = %d", i,  a[i] );
               }

           }
     }

}

I think that's pretty good! I can say a thing or two, however, that may help you improve it.

1 -- The use of static variables. It's not forbidden, but you should avoid this. Now, how would you, seeing as your solution is recursive in nature, and you need shared data between calls?

The general approach is to use a second function, that wraps the recursive call, and passes extra parameters to it. In your case:

void eachLevelSum(struct tree*);
static void eachLevelSumRecursive(struct tree*, int level, int* results);

And then, something like:

void eachLevelSum(struct tree* t) {
    int results[100];
    eachLevelSumRecursive(t, 0, results);

    return;
}

Then in your recursive function, whenever you go into recursion, you can pass the level parameter as level + 1 instead of doing level++ and level-- =D like this:

eachLevelSumRecursive(t->left, level + 1, results);
eachLevelSumRecursive(t->right, level + 1, results);

Note this is not only a bit cleaner, it has other advantages. For example, this approach can be used in a multithreaded environment, while the other one can't, since it relies on static variables.

2 -- You may want to further encapsulate your tree using typedefs, and functions that alter the structure. If you want more information on this, ask away. It's not at all necessary for your excercise, though.

3 -- Remember function names usually begin with lowercase letters.

And that's everything I have to say, your code is pretty clean! Congratulations!

Your code seems to do it correctly. In English your logic states -

For every level that you descend into the tree (both left and right), keep track of your depth and add data to a global sum-tracking variable a.

Unless you make significant changes to your structure - that's the only way to do it (that I can think of)

I would avoid using level as a global variable. In this particular case, it doesn't matter that much as there is no complication of threading or anything like that. But it's good to make it a habit to avoid using global variables.

It's always preferred to use a local variable than a global one unless you have to use a global variable and you need to be careful.

I would add level as a argument in the method, and instead of doing level++ and level--, I'll simply pass level+1 to the method call.

I think your code is good.

As an alternative, you can use BFS search: http://en.wikipedia.org/wiki/Breadth-first_search. Here is sample C# code

    class Tree
    {
        public int data;
        public Tree Left;
        public Tree Right;


            static int[] levels = new int[100];

            static void EachLevelSum(Tree root)
            {
                // keeps track of each tree node's level
                Dictionary<Tree, int> treeLevels = new Dictionary<Tree,int>();
                treeLevels.Add(root, 0);

                // Do a BFS search and update the level of each node
                Queue<Tree> trees = new Queue<Tree>();
                trees.Enqueue(root);

                while (trees.Count != 0)
                {
                    Tree node = trees.Dequeue();
                    int level = treeLevels[node];
                    if (node.Left != null)
                    {
                        treeLevels.Add(node.Left, level + 1);
                        trees.Enqueue(node.Left);
                    }
                    if (node.Right != null)
                    {
                        treeLevels.Add(node.Right, level + 1);
                        trees.Enqueue(node.Right);
                    }
                }
                foreach (Tree node in treeLevels.Keys)
                {
                    int level = treeLevels[node];
                    levels[level] += node.data;
                }

            }
    }