Merge two trees on equal nodes

Question

Nodes are equal when their IDs are equal. IDs in one tree are unique. On the schemas, IDs of nodes are visible.

Consider tree1:

root
  |
  +-- CC
  |   |
  |   \-- ZZZ
  |        |
  |        \-- UU
  |
  \-- A
      |
      \-- HAH

And tree2:

root
  |
  +-- A
      |
      +-- ADD
      |
      \-- HAH

I would like that merge(tree1, tree2) will give this:

root
  |
  +-- CC
  |   |
  |   \-- ZZZ
  |        |
  |        \-- UU
  |
  \-- A
      |
      +-- HAH
      |
      \-- ADD

How to do it?

Node has typical methods like getParent(), getChildren().

Order of the children doesn't matter. So, the result could be also:

root
  |
  +-- A
  |   |
  |   +-- ADD
  |   |
  |   \-- HAH
  |
  \-- CC
     |
     \-- ZZZ
          |
          \-- UU

If nodes are unordered, I see no alternative but to select one tree as the survivor then iterate over the other tree and add nodes from it to the first tree that don't already exist. — 500 - Internal Server Error, Jul 28 '14 at 21:46

score 3 · Accepted Answer · answered Jul 29 '14 at 19:51

3

My proposition in pseudocode. Comments are more than welcome.

merge(tree1, tree2) {
    for (node : tree2.bfs()) { // for every node in breadth-first traversal order
        found = tree1.find(node.getParent());     // find parent in tree1
        if (found == null)                        // no parent?
            continue;                             // skip it, it's root
        if (!found.getChildren().contains(node))  // no node from tree2 in tree1?
            found.add(node);                      // add it
    }
    return tree1;
}

answered Jul 29 '14 at 19:51

Adam Stelmaszczyk

19,665
4
70
110

I have same question. Is it possible to do that in SQL directly? Thanks – R. Salehi Apr 13 '20 at 17:49
Yes, it is possible. Have a look at https://stackoverflow.com/questions/13997365/sql-joins-as-venn-diagram (full outer join) – Lubo May 11 '22 at 20:02

score 1 · Answer 2 · answered Jul 28 '14 at 21:48

The basic algorithm is not hard:

def merge_trees (t1, t2):
  make_tree(map(merge_trees,assign(getChildren(t1),getChildren(t2),tree_similarity)))

make_tree(children): create a tree with the given list of children
map(f,list): calls function f on each element of list and return the list of return values
assign(list1,list2,cost_function): implements the Hungarian algorithm, returning the list of matched pairs

The trick is in defining tree_similarity which would have to call assign recursively.

In fact, the efficient implementation would have to cache the return values of the assign calls.

Merge two trees on equal nodes

2 Answers2