The Stern-Brocot tree gives a representation of (Q+,<) as infinite binary search tree. One can create another infinite binary search tree with 0 on top, positive rationals on right and negative ones on left. This gives a representation of (Q,<) as an infinite binary search tree. If we remove 0, then we get a sum of two trees ("two trees side by side"). The problem is to create an order isomorphism between the tree corresponding to (Q,<) and sum of two trees corresponding to (Q-{0},<).
These two trees can be merged into one as follows: let root(T), left(T), right(T) be the root, left subtree and right subtree of a tree T. The merge is defined recursively by:
root(T1)
merge(T1,T2) = / \
left(T1) root(T2)
/ \
merge(right(T1),left(T2)) right(T2)
(to be precise, this definition is coinductive)
The Stern-Brocot tree is Euclidean algorithm inside, so complexity aspect you seem to be interested in should be easy.