CODEWITHSUNDEEP
searchtreetraversal
Meow
Meow

Reputation: 19071

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

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 breadth 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 ++;
}

}

Upvotes: 3

Views: 11906

Answers (8)

izum286
izum286

Reputation: 35

int sumOnSelectedLevel(BNode node, int k){
            if(k==0) return node.data;
            int left = node.left == null? 0: sumOnSelectedLevel(node.left, k-1);
            int right = node.right == null? 0: sumOnSelectedLevel(node.right, k-1);
            return left+right;
        }

also handles NullPionterException.

Upvotes: 1

RobieKotlety
RobieKotlety

Reputation: 1

Simple recursive algorithm. The current level yields always 0 when calling method.

public int SumSameLevelNodes(int levelToFind, int currentLevel)
    {
        if (this == null)
            return 0;
        int sum = 0;
        if (currentLevel == levelToFind)
            sum = this.value;
        if (this.lNode != null && currentLevel < levelToFind)
        {
            sum += lNode.SumSameLevelNodes(levelToFind, currentLevel + 1);
        }
        if (this.rNode != null && currentLevel < levelToFind)
        {
            sum += rNode.SumSameLevelNodes(levelToFind, currentLevel + 1);
        }
        return sum;
    }

Upvotes: 0

Shivani Sabhlok
Shivani Sabhlok

Reputation: 1

    public static void LevelSum(Node root, int level)
    {
        Queue<Node> q = new Queue<Node>();
        q.Enqueue(root);
        --level;

        while (true)
        {
            int count = q.Count;
            while (count > 0 && level > 0)
            {
                var temp = q.Dequeue();
                if (temp.Left != null)
                    q.Enqueue(temp.Left);
                if (temp.Right != null)
                    q.Enqueue(temp.Right);
                count--;
            }
            if (level == 0)
            {
                count = q.Count;
                var sum = 0;
                while (count > 0)
                {
                    sum += q.Dequeue().data;
                    count--;
                }
                Console.WriteLine(sum);
                return;
            }
            else if (level > 0)
                level--;
            else
                return;
        }
    }

Upvotes: 0

Alex Hawkins
Alex Hawkins

Reputation: 604

Here is something similar that I had to implement for an interview question. Hopefully this helps.

//Can you write me a function that returns an array of all the averages of the nodes 
//at each level (or depth)??


BinarySearchTree.prototype.nodeAverages = function() {
    var node = this.root;
    var result = {};
    var depthAverages = [];

    var traverse = function(node, depth) {
        if (!node) return null;
        if (node) {
            if (!result[depth])
                result[depth] = [node.value];
            else
                result[depth].push(node.value);
        }
        //check to see if node is a leaf, depth stays the same if it is
        //otherwise increment depth for possible right and left nodes
        if (node.right || node.left) {
            traverse(node.left, depth + 1);
            traverse(node.right, depth + 1);
        }
    };
    traverse(node, 0);

    //get averages and breadthFirst
    for (var key in result) {
        var len = result[key].length;
        var depthAvg = 0;
        for (var i = 0; i < len; i++) {
            depthAvg += result[key][i];
        }
        depthAverages.push(Number((depthAvg / len).toFixed(2)));
    }
    return depthAverages;
};

//Tests
var bst = new BinarySearchTree();
bst.add(10).add(20).add(30).add(5).add(8).add(3).add(9).add(7).add(50).add(80).add(98);
console.log(bst.nodeAverages()); //[ 10, 12.5, 13.67, 22, 80, 98 ]

Upvotes: 0

Chris
Chris

Reputation: 26878

You can actually avoid recursion, and still use a Breadth-First Search. The way to do that, is keeping the level (depth) of each node. Initially, you just set the root's level to be 0. Now, while doing the BFS, when you move from a node u to a node v, you set depth[v] = depth[u] + 1. To keep the depth, you either use a regular array, or add use another extra element in the BFS queue. Here is pseudocode of a function that finds the sum of values of nodes at depth d in a binary tree with n nodes, where I added another element to the queue to represent the depth:

int findSum(d) { 

    ans = 0;
    q = new Queue(); //define the queue
    q.push(root, 0); //insert the root, which has depth 0.

    while(! q.empty()) {
        current_node = q.top().first, current_depth = q.top().second; //Get the current node and its depth
        q.pop(); //remove the current node from the queue

        if(current_depth == d)
            ans += current_node -> value; //if the current node is on the required depth, then add its value to the answer

        if(current_node -> left != NULL)
            q.push(current_node -> left, current_depth + 1); //add the left child to the queue, which has a depth of one more than the current depth

        if(current_node -> right != NULL)
            q.push(current_node -> right, current_depth + 1); //add the right child to the queue, which has a depth of one more than the current depth
    }
    return ans;
}

Upvotes: 2

Kshitij Banerjee
Kshitij Banerjee

Reputation: 1748

int sum(Node node , int Level)

`{ if(level==depth)
        return Level;
    else
    return ( sum(node.left, Level+1), sum(node.right, Level+1)`}

Upvotes: 0

Igor Krivokon
Igor Krivokon

Reputation: 10275

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).

Upvotes: 10

Jack
Jack

Reputation: 133557

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.

Upvotes: 2

Related Questions