Thursday, August 4, 2011
Merge the two Binary Search Trees in time O(log m + log n)
You are given two height balanced binary search trees T and T', storing m and n elements respectively. Every element of tree T is smaller than every element of tree T'. Every node u also stores height of the subtree rooted at it. Using this extra information how can you merge the two trees in time O(log m + log n) (preserving both the height balance and the order)?
Labels:Data
Amazon Interview
Subscribe to:
Post Comments
(
Atom
)
No comments :
Post a Comment