If we want to remove assumptions in finding LCA(a,b).
i.e.
Assumption 1 - both and b are present in the tree.
Assumption 2 - all keys are unique.
How do we remove both the assumptions…?
If we want to remove assumption 1, do we have to traverse the whole tree and check if a and b, both are present… It will not be efficient, I guess. Is there any other method?.
Also If duplicates are present in tree, how do we resolve this problem?
Video reference – Lowest Common Ancestor(LCA).
@sanjit_15
for assumption 1, you can put some flags while calculating the LCA that a and b is present. The method you suggested is also equally efficient asymptotically.
For assumption 2, It does not make any sense if there are multiple keys of same values, so you dont know which LCA you have to find. However, in this case, the question would be modified, you won’t be given int a,int b but TreeNode* a, TreeNode* b and that will have to be unique, Since they are the addresses of the node. In this also, the methods remain almost same. Just in case of comparing values, you compare nodes.
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.