Jan 312017
 

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)