How to find sum of node's value for given depth in binary tree?
- by masato-san
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 ++;
}
}
