LCA of array

Given a tree of N nodes rooted at 0. You are given an integer array A of size N - 1 where A[i] denoting parent of node i + 1 and an integer array B of size M containing some nodes. Find Least Common Ancestor of the array B.

Lowest Common Ancestor: Let T be a rooted tree with N nodes. Then the lowest common ancestor for an array of nodes U {u0, u1…uM-1} is the lowest node, v, for which subtree rooted at v contains all the nodes in array U.

Input Format:

    First line of input contains an integer array A denoting parent of i + 1th node
    Second line of input conatins an integer array B denoting the array for which LCA is to be found

Output Format:

    return a single integer denoting the LCA of B

Constraints:

    2 <= N <= 100000
    1 <= M,A[i],B[i] <= N

For Example:

Input 1:
    A = [0, 1, 1] B = [2, 3]
Output 1:
    1
Explanation 1:
    LCA of [2, 3] is 1.
Input 2:
    A = [0, 0, 0, 0] B = [1, 2, 1]
Output 2:
    0
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving LCA of array on Interview Code Editor
Sign Up
to access hints and editorial solutions for LCA of array

Discussion


Loading...
Click here to start solving coding interview questions