Question

a.)  Let T be a binary tree with n nodes. Define the lowest common ancestor (LCA) between two nodes v and w as the lowest node in T that has both v and w as descendants. Given two nodes v and w, write an efficient algorithm, LCA(v, w), for finding the LCA of v and w. Note: A node is a descendant of itself and v.depth gives a depth of a node v.

b.) What is the running time of your algorithm? Give the asymptotic tight bound (Q) of its running time in terms of n and justify your answer.

Answer 1

I am writing code in c++

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
       if(root==NULL||root==p||root==q)
           return root;
        TreeNode* left=lowestCommonAncestor(root->left,p,q);
        TreeNode*right=lowestCommonAncestor(root->right,p,q);
        if(left&&right)
            return root;
        return left!=NULL?left:right;
      
    }

Above function will return LCA of node p and q in the binary tree with root node as root.

b) Running time of algorithm will be O(n) as in worst case height of binary tree can be atmost n.