Discussion on Lazy White Falcon Challenge

5 years ago+ 1 comment

Hello. Please can anyone help me with this problem? I'm getting a timeout for the testcase with 100000 queries. I suspect the problem is from my algorithm to calculate the sum. The code is below:

int sumPath(Node* x, Node* y) {
    int sum = 0;
    // while x is on a level below y, ascend while adding the values to sum
    while (x->level > y->level) {
        sum += x->data;
        x = x->parent;
    }
    // while y is on a level below x, ascend while adding the values to sum
    while (y->level > x->level) {
        sum += y->data;
        y = y->parent;
    }
    //x and y are on the same level now.
    //ascend while their parents are not equal and add values to sum
    while (x != y) {
        sum += y->data;
        sum += x->data;
        x = x->parent;
        y = y->parent;
    }
    //x and y must be pointing to the same node now which is the lowest common anscestor.
    //Add the node's value to sum.
    return sum + x->data;
}

Is there a better way to implement it?

Cookie support is required to access HackerRank