1
$\begingroup$

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

}

enter image description here

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Francesco Gramano Mar 1 '15 at 2:26
  • 1
    $\begingroup$ @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). $\endgroup$ – Raphael Mar 1 '15 at 12:56
  • 2
    $\begingroup$ 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. $\endgroup$ – Raphael Mar 1 '15 at 12:57
  • $\begingroup$ @Raphael That is exactly what I want to know, the height of the tree, if there is a general formula or something like that. $\endgroup$ – S.Dan Mar 1 '15 at 13:04
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Mar 1 '15 at 13:24
1
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ $O(n)$ is a bad bound. $\endgroup$ – Raphael Mar 1 '15 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.