CODEWITHSUNDEEP
c++algorithmrecursiontreebinary-tree
argamanza
argamanza

Reputation: 1142

Trying to identify the goal of an algorithm

I have this algorithm, A and B are the addresses of of two different binary trees' roots.

Each node has a value, pointer to left sub-tree and pointer to right sub-tree.

Here is the algorithm:

foo(A,B){

    if (A == NULL){
        return B;
    }
    if (B != NULL){
        if(A->value > B->value){
            return foo(B,A);
        }
        B->left = foo(A->right,B->left);
        A->right = B;
    }
    return A;
}

I did manage to understand it's merging tree B to the right sub-tree of tree A, however i did not manager to understand the regularity of the values.

Hope you could help me with this one, thanks!

Upvotes: 3

Views: 89

Answers (1)

Jeffrey L Whitledge
Jeffrey L Whitledge

Reputation: 59533

I believe the intent is to take two sorted binary trees and combine them into a single sorted binary tree.

The key is the comparison if(A->value > B->value). This branch ensures that the A parameter will always contain the lesser value at the point in which the subtrees are merged, which forces an ordering on the result.

Since A->left and B->right are never traversed by this algorithm, there appears to be the some additional requirements on the two trees provided. One possibility is that they are expected not to have overlapping ranges. That is, the smallest value of one tree must be greater than the largest value of the other. Or the requirement may be some other thing similar to this involving the contents of the subtrees. Or perhaps the type of the value is restricted to two values, like a Boolean.

Upvotes: 9

Related Questions