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

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;
}
}
}


}

• If whatever language you plan to use to implement this should have it as a feature, you should take advantage of tail-call optimization. It would reduce your space complexity to O(1) (while still making a simple solution with recursion) Mar 1, 2015 at 2:26
• @FrancescoGramano While that may be true in the real world, such things only make the code harder to understand and analyse (in the conceptual stage).
– Raphael
Mar 1, 2015 at 12:56
• The runtime should be bounded in the height of the tree. If you have parent links, just move "up" from the nodes and check for a common node.
– Raphael
Mar 1, 2015 at 12:57
• @Raphael That is exactly what I want to know, the height of the tree, if there is a general formula or something like that. Mar 1, 2015 at 13:04
• If your tree implementation is not particularly useless, there's a simple linear-time recursive algorithm for determining height. There is no general formula, since the height of a binary tree with $n$ nodes can be anywhere between $\lceil \log_2(n) \rceil$ and $n$. For your problem, the level of the input nodes is relevant, which can be (tightly) bounded from above by the height of the tree.
– Raphael
Mar 1, 2015 at 13:24

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

• I think the op wants in terms of node, so it's just $O(n^2)$
– w00d
Mar 1, 2015 at 1:14
• A bound in terms of the height of tree is more meaningful here.
– Raphael
Mar 1, 2015 at 12:57

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.

• $O(n)$ is a bad bound.
– Raphael
Mar 1, 2015 at 12:56