CODEWITHSUNDEEP
algorithmtreebig-otime-complexitybinary-search-tree
Daniel Cook
Daniel Cook

Reputation: 1896

Merging two BSTs together in O(max(h1, h2)) time

Is there a way to do this? In other words, is there a way to know which tree has the smaller/larger height without knowing the height themselves? That way we would know which tree we need to pick the room from. Note that all the elements in the first tree are smaller than all the elements in the second tree.

h1 and h2 are the heights of the trees the height of the merged new tree needs to be max(h1 , h2) + 1

Upvotes: 0

Views: 376

Answers (2)

David Eisenstat
David Eisenstat

Reputation: 65458

Remove the least element from T2 and make it the root of a tree with T1 as the left subtree and the rest of T2 as the right. max(h1, h2) is just a convenient bound on the length of T2's left spine. We can actually get an algorithm that runs in time O(min(h1, h2)) by traversing T1's right spine and T2's left spine in a dovetailed fashion and then executing the appropriate mirror image of this algorithm when the greatest of T1/least of T2 is discovered.

Upvotes: 3

ghui
ghui

Reputation: 166

I think you have to explicitly find the heights of the trees. Without more specific info, there just isn't anything else you can do. You can find the height of a tree recursively in O(n) time where n is the number of nodes in the tree.

Upvotes: 0

Related Questions