The Stern-Brocot tree gives a representation of (Q<sup>+</sup>,<) 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][1])

The Stern-Brocot tree is Euclidean algorithm inside, so complexity aspect you seem to be interested in should be easy.


  [1]: http://mathoverflow.net/questions/740/co-induction-understanding