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.


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:


// 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>