CODEWITHSUNDEEP
javaalgorithmdata-structurestree
Aditya
Aditya

Reputation: 1268

How to merge multiple trees by retaining only those nodes which are common to all the trees

so I have two to three Trees that I generate during execution of some code. Each node of this tree has this property that it will have a minimum of 0 children to a maximum of 8 children. So I guess that you are able to get the picture of a complete tree of this sort, that has at level 0 a single root node. At level 1 8 nodes at level 2 64 nodes and so on. Each of the children nodes of a parent are numbered from 0 to 7 which I store on them as a byte integer type in java, btw I am making this in java.

Now I need to merge these two to three tree's that I have generated and I do it level wise completely disregarding the children of a given node. If at a level for the three tree's say at level 1, if tree 1 has 4,5,6 and tree 2 has 5,6,7 and tree 3 has 2,5,6 my resultant tree should have 5,6 as it is common to all the three tree's. I am not concerned if the tree 1's 5th node has 4 children and the same 5th node at that level in tree 2 has 3 children. if a node is labeled 5 at a level it is suppose to be identical to the node labeled 5 at the same level in a different tree irrespective of the number of children it has or if the children are same or not.

So to state what I mentioned in second paragraph visually so as to ensure no ambiguity I am also enclosing these three diagrams. The first two are merged to give the third tree.enter image description here

And please I have all the time in the world to make this, and this is for a personal purpose and I am trying to learn something here, so please don't suggest any libraries.

The solution am thinking of involves a single queue for each tree and doing a level order traversal on these three trees and adding nodes that I encounter to the queue. and right before I start adding children of a given node I see what is common to these three queues ! and I set the common part nodes in my resultant tree. But I was wondering if there is a solution more efficient than this.

Upvotes: 2

Views: 2159

Answers (1)

templatetypedef
templatetypedef

Reputation: 373012

Assuming the trees and children are in the same relative order in both cases, you can merge the trees together using a simple recursive algorithm:

  • Merging together an empty tree and any tree yields the empty tree.
  • Merging together trees with different roots yields the empty tree.
  • Merging together two trees with the same root r and children c1, ..., cn and d1, ..., dn is done by producing a new tree with root r whose children are the merged ci / dj pairs for ci and di that have the same root value.

Hope this helps!

Upvotes: 3

Related Questions