What is Deepest Common Ancestor

[nirwan]

I want to find the Deepest Common Ancestor (DCA) in a binary tree (non AVL).

I do not find any document talking about DCA algorithm. When I googled found lower common ancestor (LCA). Not sure if both are the same algo.

Can you please guide either DCA & LCA Algo are same or different? If different then how to calculate the DCA in a binary tree?

[razzle]

Well, why do you want to find the deepest common ancestor if you don't know what it is?

But if you ask me I'd say deepest, lowest, lower, first, closest etcetera all refer to the same ancestor.

[nirwan]

Thanks Razzle.

I'm working on a college project & I need to simplify the 'Token processing'. Each token is of 32 Bit.
We need to make sure that all the lookup should performed in a predicted time.

I want to find the common Ancestor for the newly added node into Binary Tree (non AVL). Also if there any change in existing pairs due to new one.

In previous project I had worked on JavaScript & during that time I had heard about commonAncestorContainer property of Range objects which returns deepest node that is ancestor of both boundary points.

I'm looking to implement function in C++ which can give the common upper bits & store the nodes into Tree.

Please let me know both LCA & DCA give the same result in this case or any other better way to solve this problem.