2

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.

Aditya
  • 1,240
  • 2
  • 14
  • 38
  • A -1 and no mention of why he is giving me a -1 :| Is this question ambiguous in any way ? Have I left out any vital information ? Have I posted this in the wrong stack exchange site ? This is a programming question and I can't think of any reason why it deserves a -1 ! – Aditya Jan 15 '14 at 23:47
  • Question seems ok to me. Traversing the tree left aside you just want to find the common part of two sets of children ([4, 5, 6] + [1, 2, 3, 4, 5, 6] = [4, 5, 6])? http://stackoverflow.com/questions/2851938/efficiently-finding-the-intersection-of-a-variable-number-of-sets-of-strings – zapl Jan 16 '14 at 00:21
  • That is exactly the problem I wanted to highlight @zapl by the figure. you see [4,5,6] from set A could be or could not be same as [4,5,6] from the second set. They are same if they are from the same parent. Now I could store the parent id as well in the node. So it would be [4-4,4-5,4-6,5-1,5-2,5-3] and [4-1,4-2,4-3,4-4,4-5,4-6]But for 8 levels this tree occupies a whopping 33MB for ram. so an extra 32 bit long pointer on a node would make it 66mb ! – Aditya Jan 16 '14 at 00:33
  • 1
    Each node can have a `Set` of `Node` as children. Just find a matching node, intersect the sets and recurse into the remaining children. – zapl Jan 16 '14 at 00:39

1 Answers1

3

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!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065