I have a few different trees, which resemble what the AST that compilers often deal with.
( (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.
( ( (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