Given is a binary tree and a LCA , find the number of pair of nodes which have this LCA?

Question

Consider an infinite binary tree defined as follows.

For a node labelled v, let its left child be denoted 2*v and its right child 2*v+1. The root of the tree is labelled 1.

For a given n ranges [a_1, b_1], [a_2, b_2], ... [a_n, b_n] for which (a_i <= b_i) for all i, each range [a_i,b_i] denotes a set of all integers not less than a_i and not greater than b_i. For example, [5,9] would represent the set {5,6,7,8,9}.

For some integer T, let S represent the union [a_i, b_i] for all i up to n. I need to find the number of unique pairs (irrespective of order) of elements x,y in S such that the lca(x,y) = T

(Wikipedia has a pretty good explanation of what the LCA of two nodes is.)

---

For example, for input:

A = {2, 12, 11}
B = {3, 13, 12}
T = 1

The output should be 6. (The ranges are [2,3], [12,13], and [11,12], and their union is the set {2,3,11,12,13}. Of all 20 possible pairs, exactly 6 of them ((2,3), (2,13), (3,11), (3,12), (11,13), and (12,13)) have an LCA of 1.)

And for input:

A = {1,7}
B = {2,15}
T = 3

The output should be 6. (The given ranges are [1,2] and [7,15], and their union is the set {1,2,7,8,9,10,11,12,13,14,15}. Of the 110 possible pairs, exactly 6 of them ((7,12), (7,13), (12,14), (12, 15), (13,14) and (13,15)) have an LCA of 3.)

Answer 1

Well, it is fairly simple to compute the LCA of two nodes in your notation, using this recursive method:

int lca(int a, int b) {
    if(a == b) return a;
    if(a < b) return lca(b, a);
    return lca(a/2, b);
}

Now to find the union of the sets, we first need to be able to find what set a particular range represents. Lets introduce a factory method for this:

Set<Integer> rangeSet(int a, int b){
    Set<Integer> result = new HashSet<Integer>(b-a);
    for(int n = a; n <= b; n++) result.add(n);
    return result;
}

This will return a Set<Integer> containing all the integers contained in the range.

To find the union of these sets, just addAll their elements to one set:

Set<Integer> unionSet(Set<Integer> ... sets){
    Set<Integer> result = new HashSet<Integer>();
    for(Set<Integer> s: sets)
        result.addAll(s);
    return result;
}

Now, we need to iterate over all possible pairs in the set:

pairLcaCount(int t, Set<Integer> nodes){
    int result = 0;
    for(int x: nodes)
        for(int y: nodes)
            if(x > y && lca(x,y) == t) result++;
    return result;
}

Everything else is just glue logic, methods to convert from your input requirements to the ones taken here. For instance, something like:

Set<Integer> unionSetFromBoundsLists(int[] a, int[] b){
    Set<Integer> [] ranges = new Set<Integer>[a.length];
    for(int idx = 0; idx < ranges.length; idx++)
        ranges[idx] = rangeSet(a[idx], b[idx]);
    return unionSet(ranges);
}