Vertical distance (Vertical Level)of a Node from root

Given a Binary Tree and a Node,

Write a function that return the vertical distance of that node from root of the tree. The vertical distance of a node is computed as below:

• Then the vertical distance of root is 0.
• The vertical distance of right node is distance of root+1.
• The vertical distance of left node is distance of root-1.

For example, if the binary tree is as given below:

Then vertical distance of Node-B from root is -1. E is at a vertical distance 0 from the root (we move one step left and then one step right, hence the net vertical distance from root is zero).

Solution:

The algorithm is simple, we pass the distance of current root as a parameter to the function (initially zero). When we move in the left sub-tree, we decrement the distance by 1 and when we move to the right sub-tree, then we increment the current distance.

If we could not find the node that we are looking for, then we return some value to indicate that we did not find the node (in this example, I am using INT_MIN, assuming that this value will never be a valid value).

Code:

// Return the vertical distance of node with value v
// from root of the tree pointed to by r.
// distance is initially 0.
int verticalDistance(Node* r, int v, int distance)
{
    if(r == NULL){
        return INT_MIN;
    }
    if(r->data == v)
        return distance;
    int dist = verticalDistance(r->left, v, distance-1);
    // Element found in left tree.
    if(dist != -1)
        return dist;
    return verticalDistance(r->right, v, distance+1);
}

If INT_MIN is a valid value of the Vertical Distance, then we may have to return two values (a pair) from the function 

1. A Boolean value indicating whether or no the value is found in the tree.

2. If the first return value is true, then this second value returns the Vertical Distance.