# How to merge a lot of trees into one single graph?

I have a few different trees, which resemble what the AST that compilers often deal with.

For example:

tree 1

( (a, b), (c, d) )

Imagine that each tree split represents the function "add", then tree 1 simply says: add a and b, then add c and d, in the end, add the sum of these 2 sums as the final result.

tree 2

( ( (a, b), (c, d) ), (e, f) )

obviously, I can merge tree 1 into tree 2, because tree 2 is simply constructed by adding a sibling (e, f) to tree 1.

By doing so, I don't need to re-visit a, b, c , d twice, I can simply add e and f, and add the result to the result of tree 1, to get the result of tree 2.

If I have a lot of these kind of trees, with overlapping (redundant sub-subtrees), is there an algorithm that can automatically create a graph that covers all the computation in the most efficient way ?

PS: all the trees share the same set of leaf,in this case, a b c d e f. Some trees are taller (deeper), some are shallower.

PS2: tree are not necessarily binary trees. A tree could have multiple

PS3: there could be a tree like ( (a,b), (g,h) ), i can still be partially merged with tree 1

Yes, this is sort of common subexpression elimination.

Simple approach for binary trees: introduce nodes 1 for a ... 6 for f.

Traverse your trees. When you have new pair like (1, 2) or (4, 5) introduce for them new nodes like 7 and 8, when you hit old pair, add edge from it.

You will need unordered map from pair of nodes to node, representing this pair:

(1, 2) -> 7
(3, 4) -> 8
(7, 8) -> 9
etc...


More on CSE avaliable by following links from wikipedia

If tree is not binary tree, first make it binary tree with first child / right sibling procedure. CSE in compilers most often is done on three-address code (like GIMPLE in GCC), i.e. on binary expressions only just because it is really more convenient