Is there a way to find path length to a node from root in a binary tree?

Question

I went through the algorithm’s for finding the LCA of two nodes in a binary tree (let’s say the values are random – not a binary search tree) and I chose the method where the path to root is stored in an array. That is, an array stores the parent values from one node to the root and the same is done to the second node and finally the arrays are compared to find the first mutual parent.

I got stuck when finding the time complexity of this algorithm. I have a feeling that, it depends on the path length of a node to the root. Is there a generalised equation for the path length of a binary tree? If not, how can I compute the time complexity of this algorithm?

PS-I want to find the time complexity wrt to n=number of nodes/elements

Node findLCA(BT tree, Node N1, Node N2){
    Array parentsN1;
    Array parentsN2;
    while(N1.parent != null){
        parentsN1.append(N1.parent)
        N1=N1.parent;
    }
    while(N2.parent != null){
        parentsN2.append(N2.parent)
        N2=N2.parent;
    }
    for(i in parentsN1){
        for(j in parentsN2){
            if (i==j) return i;{
                return null;
            }
        }
    }

}

Answer 1

The worst case scenario for the algorithm is when you pick two nodes, N1 and N2 that have the longest path to the root node. In your example, two nodes whose common ancestor is J. Say the length of the path of N1 and N2 is n and m. Then the first while is O(n), the second one O(m) and finally the nested loop is O(nm). So O(n) + O(m) + O(nm) = O(n*m).

Answer 2

Your solution is $O(n^2)$ and thus your prof won't be happy with it. The followings runs in $O(n)$ (it is better when the tree is balanced and thus running time can be bounded better such as by $O(\log n)$):

public Node getLCA(Node n1, Node n2) {
    int heightDiff = n1.height - n2.height;
    if (heightDiff == 0) {
        if (n1 == n2) {
            return n1;
        } else {
            return getLCA(n1.parent, n2.parent);
        }
    } else {
        Node upperNode;
        if (heightDiff > 0) {
            upperNode = walkUp(n1, heightDiff);
            return getLCA(upperNode, n2);
        } else {
            upperNode = walkUp(n2, Math.abs(heightDiff));
            return getLCA(n1, upperNode);
        }
    }
}

private Node walkUp(Node node, int heightDiff) {
    Node ret = node;
    for(int i = 0; i < heightDiff; i++) {
        ret = ret.parent;
    }
    return ret;
}

Computing the height of a node is $O(n)$. At each recursion, the height of at least one node changes by at least one. This means the total number of recursive calls is at most the height of the tree which is $O(n)$. Each call does a constant amount of work. This means $O(n)$ running time.