Vertical distance of a Node from root
January 31, 2017
Flip all zeros to ones
April 9, 2017

Sum of all nodes at a vertical level

Given a binary tree and a number n representing the vertical level. Write code to compute the sum of all nodes which are at vertical level n. For example, if the binary tree given is as below:

and n=-1, then the output should be 12. Because Nodes at level =1 are 7 and 5 and 7+5 = 12.

Solution:

We have seen the logic of computing vertical distance of a node from the root in this post.
we use similar logic, we traverse the entire tree and if a node is at vertical level n, then its value is added to the sum. Let’s have a look at the code:
Code:

// n - level whose sum we want to compute.
// curLevel - vertical level of current node.
int sumOfVerticalLevel(Node *r, int curLevel, int n)
{
    if(r == NULL)
        return 0;
    int sum = 0;
    if(curLevel == n)
        sum += r->data;
    // Adding all nodes in left subtree at
    // vertical level n
    sum += sumOfVerticalLevel(r->left, curLevel-1, n);
    // Adding all nodes in right subtree at
    // vertical level n
    sum += sumOfVerticalLevel(r->right, curLevel+1, n);
    return sum;
}

The initial value of curLevel is zero (current level or root node). The time taken by this function is O(n).
 

Leave a Reply

Your email address will not be published. Required fields are marked *