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