Lowest common ancestor

#1

in this question we are making two list one for 1st number and one for second number which contains the all ancestors of that number and when we are searching in the list for lowest comment ancestor the worst time complexity will be order of n^2

#2

@shampblocks no it will be O(n), we can find parent of every node in O(n) (single traversal) now, you need to find the ancestors of p, and q, in two arrays, we can do this using parents, simply, again this will be done in O(n) only.(two separate for loops)
Now our only task left is to iterate over the both arrays simultaneously, (use a single for loop) iterate till the elements are same as soon as you encounter different element stop, and the just previous element would be LCA.
if this resolves your doubt mark it as resolved.

#3

Sir but how can we surely say that the starting elements are same in both the arrays it will not be the case which will true all the time it was just true for special. Example in video otherwise there is no guarantee that all starting jodes are same…??

#4

@shampblocks starting element will always be same, and it will always be root, for any node the path can only start from root, so even if two nodes are in different sub trees of root, they would still have root as common ancestor. For two given nodes, if we start from root and move towards the nodes then the node after which we need to follow different paths, it will be our LCA. Try making any tree and try to follow the procedure you will always get same nodes in begining.
If this resolves your doubt mark it as resolved.

#5

Oh yess you are traversing from upward I was making the list from downward and then checking the first same element can you give approach to make list of ancestor from upward…??

#6

Sir can you clear it???

#7

@shampblocks


If this resolves your doubt mark it as resolved.

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.