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
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
.