Make delicious recipes!

Merge 2 BSTs

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)

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

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Email: (Your email is not shared with anybody)

Facebook comments:

Site Owner: Sachin Goyal