First Common Ancestor of two Nodes in a Binary Tree


  • 0
    J

    Q:
    First Common Ancestor of two Nodes in a Binary Tree. It not necessary that given tree is Binary Search Tree.

              7
          10     4
        3   5   8  12
             6   9   13
    

    Find First Common Ancestor of 9,13.

    Output: 4

    Data Structure

    typedef struct TNode{
    int info;
    struct TNode *left, *right;
    } TNode;


    bool findNode(TNode *nodePtr, int info){
        if(nodePtr == NULL) return false;
        if(nodePtr->info == info) return true;
        return (findNode(nodePtr->left, info) || findNode(nodePtr->right, info));
    }
    

    TNode * Tree::findFirstCommonAncestor(TNode *tNodePtr, int firstN, int secondN){
        if(tNodePtr==NULL) return NULL;
        
        bool  leftFirstN, rightFirstN, leftSecondN, rightSecondN;
        
        leftFirstN = findNode(tNodePtr->left, firstN);
        rightFirstN = findNode(tNodePtr->right, firstN);
        leftSecondN = findNode(tNodePtr->left, secondN);
        rightSecondN = findNode(tNodePtr->right, secondN);
        
        if( leftFirstN && rightSecondN ) return tNodePtr;
        if( leftSecondN && rightFirstN ) return tNodePtr;
        
        if(((tNodePtr->info == firstN) && (leftSecondN || rightSecondN)) ||
          (((tNodePtr->info == secondN) && (leftFirstN || rightFirstN))))
            return tNodePtr;
        
        if(findFirstCommonAncestor(tNodePtr->left, firstN, secondN) != NULL) return tNodePtr->left;
        if(findFirstCommonAncestor(tNodePtr->right, firstN, secondN) != NULL) return tNodePtr->right;
        return NULL;
    }

  • 0
    B

    Algorithm to find Least Common Ancestor using recursion

    1. Let "root" be the root of given binary tree and n1 and n2 be two given nodes.
    2. If root is equal to either n1 or n2, then root is the LCA.
    3. Recursively search for LCA in left and right sub tree.
    4. If both of the recursive calls above returned non-NULL value, that means one of the node(either n1 or n2) is in left sub tree and another is in right sub tree. Hence root is the LCA.
      If suppose only right sub tree returned non-Null value than both nodes are in right sub tree and right contains LCA.
    5. If suppose only left sub tree returned non-Null value than both nodes are in left sub tree and left contains LCA.
      Time Complexity : O(n)

    Source : Program to Find Least Common Ancestor in a Binary Tree


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.