What is Deepest Common Ancestor
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3

Thread: What is Deepest Common Ancestor

  1. #1
    Join Date
    Jan 2014

    Question What is Deepest Common Ancestor

    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?

  2. #2
    Join Date
    Jul 2013

    Re: What is Deepest Common Ancestor

    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.

  3. #3
    Join Date
    Jan 2014

    Re: What is Deepest Common Ancestor

    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.
    Last edited by nirwan; January 14th, 2014 at 10:41 AM.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts

Windows Mobile Development Center

Click Here to Expand Forum to Full Width

On-Demand Webinars (sponsored)