What time in terms of Big O will it take to merge two BST's in One?
Each having no of nodes n and height O(log n) with no common element.
Resultant should be also a BST
Binary Search Trees – Merging Two Binary Search Trees
binary treecdata structures
Related Topic
- Usefulness of pre and post order traversal of binary trees
- C++ – How to Print Bottom View of a Binary Tree?
- Binary Search Tree Insertion – Handling Equal Elements
- Is it possible to speed up a hash table by using binary search trees for separate chaining
- Java – Efficiently find whether Binary Search Tree is Height Balanced or not
- Binary Search Trees – Can Two Trees Have the Same Values but Different Structures?
Best Answer
The StackOverflow post @manlio pointed out is an exact duplicate. Basically, yes, the algorithm can improved to O(n+m); the approach is to flatten the trees to sorted lists, merge them, and recreate a BST. This page also has some example code that may be of interest as well.