You have two BST, you have to merge them into a single BST, inplace and linear time.
struct Node { int val; Node *left; Node *right; Node(int v) : val(v), left(NULL), right(NULL) {} }; Node* visit(Node *root, Node **leftMin, Node **rightMax) { if (root->left == NULL && root->right == NULL) { *leftMin = root; *rightMax = root; return root; } Node *result = root; if (root->left) { Node *p = NULL; Node *q = NULL; visit(root->left, &p, &q); q->right = root; root->left = q; *leftMin = p; } else { *leftMin = root; } if (root->right) { Node *p = NULL; Node *q = NULL; visit(root->right, &p, &q); root->right = p; p->left = root; *rightMax = q; } else { *rightMax = root; } return result; } Node* changeToList(Node *root) { Node *left = NULL; Node *right = NULL; visit(root, &left, &right); return left; } Node* mergeList(Node *root1, Node *root2) { Node *p = changeToList(root1); Node *q = changeToList(root2); Node *head = NULL; Node *prev = NULL; while (p != NULL && q != NULL) { if (head == NULL) { if (p->val < q->val) { head = p; prev = p; p = p->right; } else { head = q; prev = q; q = q->right; } } else { if (p->val < q->val) { prev->right = p; p->left = prev; prev = p; p = p->right; } else { prev->right = q; q->left = prev; prev = q; q = q->right; } } } if (p != NULL) { prev->right = p; p->left = prev; } if (q != NULL) { prev->right = q; q->left = prev; } return head; } Node* changeToTree(Node *head, int len) { if (len < 1) { return NULL; } if (len == 1) { head->left = NULL; head->right = NULL; return head; } int step = len/2; Node *root = head; while (step > 0) { root = root->right; step--; } step = len/2; Node *p = head; Node *q = root->right; root->left = changeToTree(p, step); root->right = changeToTree(q, len-step-1); return root; } Node* fun(Node *root1, Node *root2) { Node *head = mergeList(root1, root2); int len = 0; Node *p = head; while (p != NULL) { len++; p = p->right; } return changeToTree(head, len); } int main(int argc, char *argv[]) { Node a(6), b(4), c(8), d(3), e(5), f(7), g(9); a.left = &b; b.left = &d; b.right = &e; c.left = &f; c.right = &g; Node *p = fun(&a, &c); return 0; }