Explanation of merge function

Question

I saw some pseudocode in some old exam and I can't really figure out what it's doing.

Can anyone explain it to me?

A and B are BST's.

Foo(A,B)
   if A= NULL
     return B
   if B != NULL
      if value[A] > value[B]
           return Foo(B,A)
      left[B] <- Foo(right[A],left[B])
      right[A] <- B
   return A

Answer 1

This is a binary search tree merge routine. If either A or B is null (representing an empty tree), it returns the other. Otherwise, it makes sure that the root of A is less than the root of B; if the roots are in the wrong order, it recurses with the arguments swapped. Then, it recursively merges the right subtree of A and the left subtree of B, and attaches the result as the left subtree of B. Finally, it attaches B as the new right subtree of A and returns A.