CareerCup

I don't think this is an inplace sorting, you're creating an altogether new tree. One way is to take one tree as base tree (I call it tree 1) and traverse the elements of tree 2 in inorder fashion, and insert the elements onto tree 1. Destroy tree 2 at the end of this operation.

The order of this operation will be O(n2) - linear.

The initial answer seems correct.

Its just from the resultant linked list the middle node would be given as root.
One disadvantage of this solution is that from the resultant tree the search operation would be O(n).
As the resultant tree would look like
4
/\
3 5
/ \
2 6
/ \
1 7

Can anyone please explain me what's the problem in "JustStarted" solution.

* Flatten trees into sorted lists.
* Merge sorted lists.
* Create tree out of merged list.

this idea is totally right, the tree can be used as list..

This is not linear as creating a tree takes O(nlgn) time. If we could create tree in O(n) time then we can do sorting in O(n) time. ;-)

we could do it in O(m+n) (m, n sizes of both bsts)
1) Covert Tree1 in to circular doubly linked list. O(m)
Search for "tree list recursion problem" for more details.
2) Convert Tree2 in to circular doubly linked list O(n).
3) Merge Tree1, Tree2 O(m+n)
4) Convert the merged circular doubly linked list to Tree. O(m+n) (Middle node can be chosen as root to make tree balanced).

Here is C code.

/**************************************************************
**
**  Auto-generated to help solve interview questions.
**
**  Question : 
    You have two BST, you have to merge them into a single BST, inplace
and linear time. 
***************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <unistd.h>

/* Define Node */
struct node {
    int data;
    struct node *left;
    struct node *right;
};
typedef struct node* ND;

/* Tree insert */
void bt_insert( ND *tree, int data)
{
    ND p,q;
    q = p = *tree;
    while(p != NULL)
    {
        q = p;
        if( data > p->data)
            p = p->right;
        else
            p = p->left;
    }
    p = (ND) malloc( sizeof(struct node ));
    p->data = data;
    p->left = NULL;
    p->right = NULL;
    if (*tree == NULL)
    {
        *tree = p;
    }
    else
    {
        if( data > q->data )
            q->right = p;
        else
            q->left = p;
    }
}
/* convert binary tree to list*/
void bt_list(ND *head)
{
    ND first, last, t, tree;
    tree = *head;

    if( tree == NULL)
        return;

    // Store right leaf as we will overwrite it..
    t = tree->right;

    // Both leafs null, just point them to trunk and return;
    if( tree->right == NULL && tree->left == NULL)
    {
        tree->left  = tree;
        tree->right = tree;
        return;
    }
    // Non null left leaf
    // Recursively, list the left tree.
    // tree should point to the last node in the list.
    if( tree->left != NULL)
    {
        bt_list(&tree->left);
        last = tree->left;
        first = last->right;
        tree->right =  first;
        tree->left = last;
        first->left = tree;
        last->right = tree;
    }
    else
    {
        first = last = tree;
        last->left = tree;
        last->right = tree;
    }
    if( t != NULL)
    {
        bt_list(&t);
        // tree is last now.
        tree->right = t->right;
        t->right->left = tree;
        t->right = first;
        first->left = t;
        *head = t;
    }
}
/* print bt */
void bt_print( ND tree)
{
    if( tree != NULL)
    {
       bt_print(tree->left);
       printf("%d \t", tree->data);
       bt_print(tree->right);
    }
}
/* print list */
void lt_print( ND tree)
{
    ND t=NULL;
    while( tree != t)
    {
        if(t == NULL)
        {
            t = tree;
        }
        printf("%d \t", tree->right->data);
        tree = tree->right;
        if( tree->right->left != tree  || tree->left->right != tree)
            printf("Broken Link");
    }
    printf("\n");
}
/* convert list to tree */
void lt_tree( ND *list)
{
    ND  first, last;
    int len=1;
    // Find mid point
    if( *list == NULL)
        return;
    last = *list;
    first = last->right;
    while(first != last)
    {
        first = first->right;
        len++;
    }
    if( 1 == len)
    {
        first->right = NULL;
        first->left  = NULL;
        return;
    }
    len /= 2;
    while(len)
    {
        first = first->right;
        len --;
    }
    // first now represents the last of new left list.
    // set the root of tree.
    *list = first->right;
    // creating left list
    first->right = last->right;
    first->right->left = first;
    // create right list only if there is a right node.
    if( (*list)->right  != first)
    {
        last->right = (*list)->right;
        last->right->left = last;
    }
    else
    {
        (*list)->right = NULL;
        last = NULL;
    }
    lt_tree(&first);
    (*list)->left = first;
    if( last != NULL)
    {
        lt_tree(&last);
        (*list)->right = last;
    }
}
/* Merge two dlls */
lt_merge(ND *l1, ND *l2)
{
    ND l=NULL;
    ND p1, p2,p, t;
    if( *l2 == NULL)
    {
        return;
    }
    if( *l1 == NULL)
    {
        *l1 = *l2;
        return;
    }
    p1 = (*l1)->right; p2 = (*l2)->right;

    while( p1 != NULL && p2 != NULL)
    {
        if( p1->data <  p2->data)
        {
             t = p1;
             p1 = p1->right;
             if( t != p1)
             {
                 p1->left = t->left;
                 t->left->right = p1;
             }
             else
             {
                 p1 = NULL;
             }
        }
        else
        {
             t = p2;
             p2 = p2->right;
             if( t != p2)
             {
                 p2->left = t->left;
                 t->left->right = p2;
             }
             else
             {
                 p2 = NULL;
             }
        }
        if( l == NULL)
        {
            t->right = t->left = t;
        }
        else
        {
            t->right = l->right;
            l->right->left = t;
            l->right = t;
            t->left = l;
        }
        l = t;
    }
    if( p1 != NULL )
    {
        t = p1->left;
        
        t->right = l->right;
        l->right->left = t;
        l->right = p1;
        p1->left = l;
        l = t;
    }
    if( p2 != NULL )
    {
        t = p2->left;
        
        t->right = l->right;
        l->right->left = t;
        l->right = p2;
        p2->left = l;
        l = t;
    }
    *l1 = l;
}
int main()
{
  int i,r;
  ND tree1 = NULL, tree2 = NULL;

  for( i =0; i < 10; i++)
  {
      r = random()%100;
      bt_insert(&tree1, r);
      r = random()%100;
      bt_insert(&tree2, r);
  }

  printf("\nTree1: ");
  bt_print(tree1);

  printf("\nTree2: ");
  bt_print(tree2);
  printf("\n");

  // convert to lists
  bt_list(&tree1);
  bt_list(&tree2);
  // merge list
  lt_merge(&tree1, &tree2);
  // revert back to a tree.
  lt_tree(&tree1);


  printf("Tree:");
  bt_print(tree1);
  printf("\n");
  return 0;
}

It's not that easy. You may violate the property of BST after the method you mentioned.

Yes, True. My above solution will violate the property of BST.
Following should do:
If BSTs are A and B then:

Merge(A,B)
{
If A has only one node, insert into B.
If rootA < rootB then
rightA = A.right
A.right = NULL
Merge(A,B.left)
Merge(rightA,B)
Else
leftA = A.left
A.left = NULL
Merge(A,B.right)
Merge(leftA,B)
}

Its not necessary that u'll end up with leaf while inserting and also its not linear. its O(mlogn) where m=|A| and n=|B| and worst is O(mn) if both the tree are right skewed having root of A is greater then rightmost child of B. or both tree are left skewed and root of A is smaller than leftmost child of B.

Ok, few points.

1. You are correct. We may not always end up in a leaf. But, if we dont end up in a lead, we may end up at a node with only one child. That, would mean the root(A) will become that child. ( depending on whether we chose to walk down the max/min path)

2. Your analysis is incorrect, since I walk through only tree(B), and just attach the root node of A to one of the nodes in B. Therefore, at most the algorithm will only walk through all nodes in B. Therefore, it is linear.

3. I think point 2 answers the skewness of the tree as well.


I will try to post a code which would explain this better.

Also, these steps could become recursive. But, still would remain linear. There is a similar algo explained at this link.

discuss.joelonsoftware.com/default.asp?interview.11.506320.10

@Tulley ,i think we will always end up at a leaf.
can u give an example when this case is not true?

Pay attention to the requirements,the algorithm must be inplace and linear time.

To make it inorder, we can modify the code of Postfix, such that instead of returning the data, it returns the address of the node. We can add this mode in the tree 2.

insertion of each node takes O(lgn) time. Total time to insert all nodes of tree(A) into tree(B) will take O(nlgn) time. This is not linear.

elegant but not linear time (also uses stack-space via recursion).

algoseekar,

intuition is to reach down to leaf-nodes by post-traversal, dettach them and insert into the second one. You need to visualize post-traversal on a simple tree and see that it tears apart the leaf nodes first so that no interval node deletion is to be handled and stuff.