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
    Posts
    2

    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
    Posts
    288

    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
    Posts
    2

    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

This is a CodeGuru survey question.


Featured


HTML5 Development Center