CODEWITHSUNDEEP
c++algorithmbinary-search-tree
mary
mary

Reputation: 919

binary search tree - get heaviest path algorithm c++

using a binary search tree I need to add to a vector all int elements of the heaviest path of the tree. for example I have 20,7,6,9,11,21 the values that should be added to the vector would be 20 ,7,9,11 I have written the implementation of the calculation of the heaviest path, but I don't know how to change it so the right elements will be added to the vector:

int Tree::maxBranch(Node* node){
    if(node==NULL)
        return 0;
    int leftSum=node->data+maxBranch(node->left);
    int rightSum=node->data+maxBranch(node->right);
    if(rightSum>leftSum){
        return rightSum;
    }
    return leftSum;     
}

Upvotes: 1

Views: 647

Answers (2)

Borealid
Borealid

Reputation: 98559

Your code as written does not keep track of the branches it's followed at all - it only gets the sum.

You should change the function to take an std::vector<int>& as an argument (note the &, for a reference type, since you need to effectively return two values).

Call it with an empty vector.

Before the line where you do the recursive call on node->left, you should save the original vector as, for instance, std::vector<int> vec_left(input_vector) and std::vector<int> vec_right(input_vector). Then pass the two copies down to the recursive calls.

Now, in the code, just before return rightSum, you should have a vec_right.push_back(node->id); input_vector = vec_right;. Just before return leftSum, you should likewise have a vec_left.push_back(node->id); input_vector = vec_left;. In English, you keep the path that was made by the branch which had the highest sum, and discard the other one.

Upvotes: 2

Henrik
Henrik

Reputation: 23324

Quick & dirty:

int Tree::maxBranch(Node* node, vector<int>& vec, bool add){
    if(node==NULL)
        return 0;
    int leftSum=node->data+maxBranch(node->left, vec, false);
    int rightSum=node->data+maxBranch(node->right, vec, false);
    if (add)
        vec.push_back(node->data);
    if(rightSum>leftSum){
        if (add)
            maxBranch(node->right, vec, true);
        return rightSum;
    }
    if (add)
        maxBranch(node->left, vec, true);
    return leftSum;     
}

Upvotes: 0

Related Questions