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);`
`}`