1

Suppose we have a set of binary trees with their inorder and preorder traversals given and where no tree is a subtree of another tree in the given set. Now another binary tree Q is given.

Find whether it can be formed by joining the binary trees from the given set(while joining each tree in the set should be considered atmost once). In this case a joining operation means: Pick the root of any tree in the set and hook it to any vertex of another tree such that the resulting tree is also a binary tree.

Can we do this using LCA (least common ancestor)? Or does it needs any special datastructure to solve?

1
  • The naïve solution would be to just traverse the first tree and insert every node into the second tree just as usual. But there is surely a better solution.
    – Philipp
    Apr 20 '16 at 9:13
1

From what i know there is no way like you mentioned to hook the vertex to some node. what you can do is to take the elements from smaller tree and insert them into the larger one.(Long method)

Or

You can do inorder traversal of 1st tree store it in array1 takes O(n) time. Apply same for 2nd tree and store in array2 O(n) time. These 2 arrays would be sorted one and hence merging them would also take O(n) time. And then use this sorted array to build BST this too will take O(n) time.

So overall it takes O(n) time.

You can lookup on geeksforgeeks for same.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.