Merge two binary search trees - PrismoSkills
Method 1 (Insert elements of first tree to second)
The value of this expression will be between mLogn and mLog(m+n-1).
http://dzmitryhuba.blogspot.com/2011/03/merge-binary-search-trees-in-place.html
Read full article from Merge two binary search trees - PrismoSkills
Solution 1:
Store inorder traversal of both trees in separate arrays -> O(m+n)
Merge two sorted arrays obtained above -> O(m+n)
Construct balanced BST from this merged array -> O(m+n)
Total order -> 3*O(m+n)
Total space complexity -> 2*O(m+n)
struct node* mergeTrees(struct node *root1, struct node *root2, int m, int n){ // Store inorder traversal of first tree in an array arr1[] int *arr1 = new int[m]; int i = 0; storeInorder(root1, arr1, &i); // Store inorder traversal of second tree in another array arr2[] int *arr2 = new int[n]; int j = 0; storeInorder(root2, arr2, &j); // Merge the two sorted array into one int *mergedArr = merge(arr1, arr2, m, n); // Construct a tree from the merged array and return root of the tree return sortedArrayToBST (mergedArr, 0, m+n-1);}void storeInorder(struct node* node, int inorder[], int *index_ptr){ if (node == NULL) return; /* first recur on left child */ storeInorder(node->left, inorder, index_ptr); inorder[*index_ptr] = node->data; (*index_ptr)++; // increase index for next entry /* now recur on right child */ storeInorder(node->right, inorder, index_ptr);}/* A function that constructs Balanced Binary Search Tree from a sorted arraystruct node* sortedArrayToBST(int arr[], int start, int end){ /* Base Case */ if (start > end) return NULL; /* Get the middle element and make it root */ int mid = (start + end)/2; struct node *root = newNode(arr[mid]); /* Recursively construct the left subtree and make it left child of root */ root->left = sortedArrayToBST(arr, start, mid-1); /* Recursively construct the right subtree and make it right child of root */ root->right = sortedArrayToBST(arr, mid+1, end); return root;}
Solution 2:
To reduce the extra space required, a better solution in O(m+n) time would be as follows:
1) Convert each BST into a sorted double linked list - O(m) + O(n) time
2) Merge the 2 SDLLs - O(m+n) time
3) Convert the resulting final SDLL into a BST - O(m+n) time
Total order -> 3*O(m+n)
Total space complexity -> 0
Method 3 (In-Place Merge using DLL)
We can use a Doubly Linked List to merge trees in place. Following are the steps.
We can use a Doubly Linked List to merge trees in place. Following are the steps.
1) Convert the given two Binary Search Trees into doubly linked list in place (Refer this post for this step).
2) Merge the two sorted Linked Lists (Refer this post for this step).
3) Build a Balanced Binary Search Tree from the merged list created in step 2. (Refer this post for this step)
2) Merge the two sorted Linked Lists (Refer this post for this step).
3) Build a Balanced Binary Search Tree from the merged list created in step 2. (Refer this post for this step)
Time complexity of this method is also O(m+n) and this method does conversion in place.
Given two Binary Search Trees(BST), print the elements of both BSTs in sorted form.
Time Complexity: O(m+n)
Auxiliary Space: O(height of the first tree + height of the second tree)
Auxiliary Space: O(height of the first tree + height of the second tree)
The idea is to use iterative inorder traversal. We use two auxiliary stacks for two BSTs. Since we need to print the elements in sorted form, whenever we get a smaller element from any of the trees, we print it. If the element is greater, then we push it back to stack for the next iteration.
// The function to print data of two BSTs in sorted ordervoid merge(struct node *root1, struct node *root2){ // s1 is stack to hold nodes of first BST struct snode *s1 = NULL; // Current node of first BST struct node *current1 = root1; // s2 is stack to hold nodes of second BST struct snode *s2 = NULL; // Current node of second BST struct node *current2 = root2; // If first BST is empty, then output is inorder // traversal of second BST if (root1 == NULL) { inorder(root2); return; } // If second BST is empty, then output is inorder // traversal of first BST if (root2 == NULL) { inorder(root1); return ; } // Run the loop while there are nodes not yet printed. // The nodes may be in stack(explored, but not printed) // or may be not yet explored while (current1 != NULL || !isEmpty(s1) || current2 != NULL || !isEmpty(s2)) { // Following steps follow iterative Inorder Traversal if (current1 != NULL || current2 != NULL ) { // Reach the leftmost node of both BSTs and push ancestors of // leftmost nodes to stack s1 and s2 respectively if (current1 != NULL) { push(&s1, current1); current1 = current1->left; } if (current2 != NULL) { push(&s2, current2); current2 = current2->left; } } else { // If we reach a NULL node and either of the stacks is empty, // then one tree is exhausted, ptint the other tree if (isEmpty(s1)) { while (!isEmpty(s2)) { current2 = pop (&s2); current2->left = NULL; inorder(current2); } return ; } if (isEmpty(s2)) { while (!isEmpty(s1)) { current1 = pop (&s1); current1->left = NULL; inorder(current1); } return ; } // Pop an element from both stacks and compare the // popped elements current1 = pop(&s1); current2 = pop(&s2); // If element of first tree is smaller, then print it // and push the right subtree. If the element is larger, // then we push it back to the corresponding stack. if (current1->data < current2->data) { printf("%d ", current1->data); current1 = current1->right; push(&s2, current2); current2 = NULL; } else { printf("%d ", current2->data); current2 = current2->right; push(&s1, current1); current1 = NULL; } } }The value of this expression will be between mLogn and mLog(m+n-1).
http://dzmitryhuba.blogspot.com/2011/03/merge-binary-search-trees-in-place.html
The simplest solution to do this is to take every element of one tree and insert it into the other tree. This may be really inefficient as it depends on how well target tree is balanced and it doesn’t take into account structure of the source tree.
// Converts tree to sorted singly linked list and appends it |
// to the head of the existing list and returns new head. |
// Left pointers are used as next pointer to form singly |
// linked list thus basically forming degenerate tree of |
// single left oriented branch. Head of the list points |
// to the node with greatest element. |
static TreeNode<T> ToSortedList<T>(TreeNode<T> tree, TreeNode<T> head) |
{ |
if (tree == null) |
// Nothing to convert and append |
return head; |
// Do conversion using in order traversal |
// Convert first left sub-tree and append it to |
// existing list |
head = ToSortedList(tree.Left, head); |
// Append root to the list and use it as new head |
tree.Left = head; |
// Convert right sub-tree and append it to list |
// already containing left sub-tree and root |
return ToSortedList(tree.Right, tree); |
} |
Read full article from Merge two binary search trees - PrismoSkills
