We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
i have returned A , but output is incorrect for testcase 2
my code
node * lca(node * root, int v1,int v2) { static node *safe; if((root -> data >= v1 && root -> data <= v2) || (root -> data <= v1 && root -> data >= v2)) safe = root; return safe; if(root -> data < v1) lca(root -> right , v1 , v2); else lca(root -> left , v1 , v2);
return safe; }
return safe; }
In this case you are not checking v2. you may lose the trail of v2 while traversing. In your decision logic your root depends on v1 as well as v2......
go for the simple code...
Consider this.
LCA is v1's address.But since you're returning only the address without storing it in some value,it is getting lost.When control gets to x it will return it's own root ie x because each parametrised "root" is local.However storing it in root updates the value of the local root with the LCA and as the chain of hierarchy goes upwards the LCA keeps getting returned.
Hello, Can someone explain below scenario
I have added below input in custom testcase for current program.
6
4 2 3 1 7 6
0 5
v1 =0 and v2 = 5 which are not present in my tree still it shows common parent as 4. and testcase shows pass.
Binary Search Tree : Lowest Common Ancestor
You are viewing a single comment's thread. Return to all comments →
i have returned A , but output is incorrect for testcase 2 my code node * lca(node * root, int v1,int v2) { static node *safe; if((root -> data >= v1 && root -> data <= v2) || (root -> data <= v1 && root -> data >= v2)) safe = root; return safe; if(root -> data < v1) lca(root -> right , v1 , v2); else lca(root -> left , v1 , v2); return safe; }
your logic is incorrect after.....
if(root -> data < v1)
lca(root -> right , v1 , v2);
else
lca(root -> left , v1 , v2);
return safe; } In this case you are not checking v2. you may lose the trail of v2 while traversing. In your decision logic your root depends on v1 as well as v2...... go for the simple code...
node * lca(node * root, int v1,int v2)
{
}
Awesome, can you please explain why assigning it to root will work correctly but fails if used as node* only for test case 2?
Thanks in advance!!
root->(right)->x->(right)->v1->(right)->v2
Consider this. LCA is v1's address.But since you're returning only the address without storing it in some value,it is getting lost.When control gets to x it will return it's own root ie x because each parametrised "root" is local.However storing it in root updates the value of the local root with the LCA and as the chain of hierarchy goes upwards the LCA keeps getting returned.
great answer...
Hello, Can someone explain below scenario I have added below input in custom testcase for current program. 6 4 2 3 1 7 6 0 5 v1 =0 and v2 = 5 which are not present in my tree still it shows common parent as 4. and testcase shows pass.
Kindly follow the constraints while creating a custom testcase :)
Please explain why assigning it as root works but when used as Node root ,iit fails the test case 2.
thanks man!!
if(Math.min(v1,v2)<=root.data && Math.max(v1,v2)>=root.data) { return root;} if(v1>root.data){ return lca(root.right, v1, v2); } if(v1