CareerCup

Find least common ancestor of two nodes, then you can find distance between them.

With languages that pass parameters with references like JAVA, your "root" variable will be changed after execution. Other than this, I think it is correct.

I agree with @nitingupta180 , once you find the least common ancestor of two nodes , you need to find the distance from the first node to LCA and from LCA to second node, then add them up.

We can do a preorder traversal on the binary tree.
Time compexity O(N), space complexity, O(log(n))

int findDistance(const Node * root, int val1, int val2)
{
    // check if the tree is empty or not
    if(root == NULL)
    {
        std::cout<<"Empty tree" << std::endl;
        return -1;
    }

    // check if the two values are equal or not, if they are
    // then the distance between the two is obviously zero
    if(val1 == val2)
        return 0;

    // have a stack to hold the nodes for back traversal
    std::stack<Node*>  stack;

    // For simplifying our code, we will make val1 < val2
    if(val2 < val1)
    {
        val1 = val1 + val2;
        val2 = val1 - val2;
        val1 = val1 - val2;
    }

    // initial distance betwen nodes is -1
    int distance = -1;

    while(!stack.empty() || root != null)
    {
        // traverse to the left of the subtree at root
        if(root != null)
        {
            if(root->val == val1)
                distance = 0;

            // if value of this node = val2, then we are done
            // return distance calculated so far
            else if(root->val == val2)
                return distance;

            stack.push(root);
            root = root->left;

            // this node might be on the path between val and val2
            // increment distance
            ++distance;
        }
        // else go right
        else
        {
            root = stack.pop();

            // this node is not on the path between val and val2
            // decrement distance
            --distance;

            root = root->right;
        }
    }
    return distance;
}

Please let me know if I have missed any corner case or if the logic needs some change

Since both the given values are present in BST, just finding out depth(root, val1)+depth(root,val2) is enough right. This will give us the answer.
May be for validation sake we can find out if the given node values are actually present or not.

it is correct ... only one missing thing I guess is +1 in the end.

return depth(root, val1) + depth(root,val2) +1