Home > programming > Merge 2 BST’s

Merge 2 BST’s


 

  • Flattening a BST into a sorted list is O(N)
    • It’s just “in-order” iteration on the whole tree.
    • Doing it for both is O(n1+n2)
  • Merging two sorted lists is into one sorted list is O(n1+n2).
    • Keep pointers to the heads of both lists
    • Pick the smaller head and advance its pointer
    • This is how the merge of merge-sort works
  • Creating a perfectly balanced BST from a sorted list is O(N)
    • The value at the middle would be the root, and recurse.
    • In our case the sorted list is of size n1+n2. so O(n1+n2)
    • The resulting tree would be the conceptual BST of binary searching the list

 

BinaryTree* sortedArrayToBST(int arr[], int start, int end) {

  if (start > end) return NULL;
  // same as (start+end)/2, avoids overflow.
  int mid = start + (end - start) / 2;
  BinaryTree *node = new BinaryTree(arr[mid]);
  node->left = sortedArrayToBST(arr, start, mid-1);
  node->right = sortedArrayToBST(arr, mid+1, end);
  return node;
}
BinaryTree* sortedArrayToBST(int arr[], int n) {
  return sortedArrayToBST(arr, 0, n-1);
}
Advertisements
Categories: programming
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: