Joining of binary trees

Question

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 datastructure to solve?

Answer 1

I think a Binary tree structure should be enough. I don't think you NEED any other special data structure.

And I don't understand how you would use LCA for this. As far as my knowledge goes, LCA is used for knowing the lowest common Ancestor for two NODES in the same tree. It would not help in comparing two trees. (which is what I would do to check if Q can be formed)

My solution in words.

The tree Q that has to be checked if it can be made from the set of trees, So I would take a top-down approach. Basically comparing Q with the possible trees formed from the set.

Logic: if Q.root does not match with any of the roots of the trees in the set (A,B,C....Z...), No solution possible.

if Q.root matches a Tree root (say A) check corresponding children and mark A as used/visited. (Which is what I understand from the question: a tree can be used only once)

We should continue with A in our solution only if all of Q's children match the corresponding children of A. (I would do Depth First traversal, Breadth First would work as well).

We can add append a new tree from the set (i.e. append a new root (tree B) only at leaf nodes of A as we have to maintain binary tree). Keep track of where the B was appended.

Repeat same check with corresponding children comparison as done for A. If no match, remove B and try to add C tree at the place where B was Added.

We continue to do this till we run out of nodes in Q. (unless we want IDENTICAL MATCH, in which case we would try other tree combinations other than the ones that we have, which match Q but have more nodes).

Apologies for the lengthy verbose answer. (I feel my pseudo code would be difficult to write and be riddled with comments to explain).

Hope this helps.

An alternate solution: Will be much less efficient (try only if there are relatively less number of trees) : forming all possible set of trees ( first in 2s then 3s ....N) and and Checking the formed trees if they are identical to Q. the comparing part can be referred here: http://www.geeksforgeeks.org/write-c-code-to-determine-if-two-trees-are-identical/