Lowest Common Ancester

#1

question–>
https://practice.geeksforgeeks.org/problems/lowest-common-ancestor-in-a-binary-tree/1#

code–>


i trying to find the last common prefix
it is not passing all testcases hep!!

#2

the testcase where the code is passing is when the root itself is a lca @mr.encoder

#3

have you taken care of that case in which both of the nodes are not present? Also we just have to pass a single node which is LCA of n1 & n2 which i can see. Give me some time to debug

#4

OKay i got your approach you are finding all the ancestor till n1 and same for n2 then finding the common lca among it ? is this your approach?

#5

hi i have taken care of if both node are not present ,when if(n1path.size()==0 or n2path.size()==0){return NULL;}

#6

yes i am doing that only

#7

We may assume that either both n1 and n2 are present in the tree or none of them is present.

#8

Bhai tum fun1 function mai pop ni kr rhe ho, If n1 is not present in subtree rooted with root, we have to remove root from our vector path.

#9

bhai i am doing it by pass by value woh apne app pop hojayaga,if we do it by pass by reference then only we have pop_back() else recursion will go back to the previous state

#10

It’s showing this while submitting for this test case
2 1
2 1 9 N N 3 10

Its Correct output is:
2

And Your Code’s output is:
10

#11

bro in compiler it is showing 2
see this

#12

Is there input of level order ? if yes are you doing the same or not?

#13

yes it is level order traverval only

#14

ha toh yaar tumahra saara code sahi hai bs ek condition add krlo jb dono node he present na ho

image
image1482×995 217 KB

Cause I have seen lcs(1,10) = 2
Lcs(9,10)=9
Lcs(3,10)=9
All are working perfectly fine except for that case where lcs(0,0) it’s giving run time error as both of them aren’t present

#15

it is taking so much time i will try tomorrow thanks for help @mr.encoder

#16

kuch bhi karu gfg mei sara testcase pass nahi ho rahe

#17

i know that’s why i don’t do gfg, i do leetcode. Moreover yaar tum krlena yeh question cause it’s important if not by doing this method then there are other method too like parent son pointer or many other you can even watch youtube video of this question as it’s a commonly asked question.

#18

i know the recursive method but this method is similar to the question root to leaf node sum
like this question–>

#19

that’s why i was trying

#20

Yeh wala krliya tha na tumhne?