How to find sum of node's value for given depth in binary tree?

Question

I've been scratching my head for several hours for this...

problem:

Binary Tree

   (0)      depth 0
   / \
  10   20   depth 1
 / \   / \
30 40  50 60  depth 2

I am trying to write a function that takes depth as argument and return the sum of values of nodes of the given depth.

For instance, if I pass 2, it should return 180 (i.e. 30+40+50+60)

I decided to use breath first search and when I find the node with desired depth, sum up the value, but I just can't figure out how to find out the way which node is in what depth. But with this approach I feel like going to totally wrong direction.

function level_order($root, $targetDepth) {
$q = new Queue();
$q->enqueue($root);

while(!$q->isEmpty) {
    //how to determin the depth of the node???
    $node = $q->dequeue();

    if($currentDepth == $targetDepth) {
        $sum = $node->value;
    }

    if($node->left != null) {
        $q->enqueue($node->left);
    }
    if($node->right != null) {
        $q->enqueue($node->right);
    }
    //need to reset this somehow
    $currentDepth ++;
}

}

Answer 1

With recursion it will be easy:

int calc_sum(node, depth)
{
  if (depth > 0)
  {
    sum = 0   
    for every children n of node
      sum += calc_sum(n, depth -1)
    return sum
  }
  else
    return node.value
}

this will compute the partial sum at depth d of a tree t as the sum of values of t.children at depth d-1. Like you were wondering you bring the remaining depth together with the subtree you are calculating as a parameter.

If you want a more efficient solution you can use dynamic programming to resolve this problem in an iterative way.

Answer 2

Just do a depth-first search recursively, keep the current level and sum the nodes at given depth.

The pseudocode:

sum(Node, Level) = 
  if (Level == 0) return Node.value;
  else return f(Node.left, Level-1) + 
              f(Node.right, Level-1).