(Please explain how you get the answer to this question.) Q. Consider two binary

Question

(Please explain how you get the answer to this question.)

Q. Consider two binary search trees A and B ( They are NOT AVL trees, just plain BSTs). BST A has x nodes, and BST B has y nodes. Assume there are no duplicates in the entire set of items in A and B. Describe the fastest algorithm to output the combined set of items in A and B in sorted (ascending) order. You can use additional array space if you need to, but no other data structure. Derive the worst case big o running time of your algorithm. (if your algorithm is NOT the fastest, it will get at most 3 points.)

Explanation / Answer

Two trees can be merged by merging there inorder traversal.
Let tree has m element, and tree B has n element

MergeTrees(A, B)

As shown above steps that Worst case time complexity will be O(m+n)

(It takes O(m+n) extra space)

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.