What if parent pointers are not available?

If parent pointers are not available, the BSTs can be converted to linked list and then merged.

1.    Convert both the BSTs into sorted doubly linked list in O(n + m) time. This produces 2 sorted  lists.

2.   Merge the two double linked list into one and also maintain the count of the total elements in O(n + m) time.

3.    Convert the sorted doubly linked list into height balanced tree in O(n + m) time.