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.) 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 data structure to solve?

  • 3
    $\begingroup$ It is not fully clear what you are asking. The merged tree should be exact $Q$ Tree? Do you start from merging inorder traversals and compare it with $Q$ inorder? Or contain same information? Does set of nodes match the $Q$ What if nodes match but tree needs rotation of some nodes? (Can be build from vertices), why would you need LCA? Does it work? What else have you tried? Can you show minimal working example? $\endgroup$ – Evil Apr 15 '16 at 14:27
  • 1
    $\begingroup$ What are your thoughts? You have an idea for an approach; have you tried it with a few examples to see if it always seems to work? Have you tried proving it works? Where did you get stuck? $\endgroup$ – D.W. Apr 15 '16 at 16:47

Your Answer

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

Browse other questions tagged or ask your own question.