[lichtenberger]

Hm, where else are Lowest Common Ancestors in tree-structures useful? Storing for instance ORDPATH/DeweyIDs allows to simply check for a common prefix (they are hierarchical node labels). I think maybe for locking in a storage system with multiple read/write transactions or to determine which of two given nodes is the firs one in preorder, which is useful for XQuery/XPath processing (to determine the so caslled document order). Can anyone think of other usages? Or for having hierarchical node labels in trees?

[htiek]

You can use lowest common ancestor queries in conjunction with suffix trees to solve a lot of interesting string problems. For example, take two indices within a string, find their corresponding suffixes in the suffix tree, and then take their LCA. That gives you an internal node corresponding to the longest string that appears starting at both indices (this is called their "longest common extension.") You can use this as a subroutine in a bunch of genomics applications.

[lichtenberger]

Thanks, great use case and I have to say I have to read about genomics... :-)

[atlassubbed]

Error-boundaries in VDOM frameworks. If you have an asynchronous diff cycle, you might get multiple errors from more than one node in a single diff cycle. One option is to bubble up errors to the nearest LCA that is an error-boundary. In general if you have marked two nodes in a tree and need to modify the smallest subtree that contains those nodes, then you will probably need to know the LCA.

[SnowflakeOnIce]

Lowest Common Ancestor shows up in graph theory, particularly to help compute dominator trees or dominator frontiers.

These problems arise in compilers that convert programs into static single assignment (SSA) form.

[danharaj]

I've seen it used in blockchain analysis and calculating the base for a three way merge operation.

[lichtenberger]

So much stuff you can learn in the computer science world. For me the blockchain still is more or less a black box, should read a book about this stuff, as it seems to be hyped everywhere ;-)

Thanks :)

[ska]

Perhaps worth starting with Merkel trees before digging into blockchain implementations.

[lichtenberger]

I'm familiar with merkle trees :-)

[lichtenberger]

Thanks for the suggestion/tip :-)